C++ में सरणी की डिग्री

मान लीजिए हमारे पास गैर-ऋणात्मक पूर्णांकों की एक सरणी nums है, इस सरणी की डिग्री वास्तव में इसके किसी भी तत्व की अधिकतम आवृत्ति है। हमें nums के एक सन्निहित सबअरे की न्यूनतम संभव लंबाई ढूंढनी है, जिसकी डिग्री nums के समान हो।

इसलिए, यदि इनपुट [1,2,2,3,1] जैसा है, तो आउटपुट 2 होगा, क्योंकि इनपुट सरणी की डिग्री 2 है क्योंकि तत्व 1 और 2 दोनों दो बार आते हैं। सबअरे जिनकी डिग्री समान है: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]। सबसे छोटी लंबाई 2 है। इसलिए उत्तर 2 होगा।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

आकार 50000 की एक सरणी freq परिभाषित करें और इसे 0 से भरें
max_ := 0
nums में प्रत्येक n के लिए:
- freq[n] को 1 से बढ़ाएं
- max_ := max(max_, freq[n]) का अधिकतम
freq सरणी को 0 से भरें।
min_ := nums का आकार
i := 0, j := -1, आकार := nums का आकार से शुरू करके j < आकार तक लूप चलाएं:
- यदि j >= 0 और freq[nums[j]] == max_, तो:
  - min_ := min(min_, j - i + 1)
  - freq[nums[i++]] को घटाएं
- अन्यथा यदि j < आकार - 1, तो:
  - j को 1 से बढ़ाएं
  - freq[nums[j]] को 1 से बढ़ाएं
- अन्यथा:
  - लूप से बाहर निकलें
min_ वापस करें

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 
class Solution { 
public: 
    int findShortestSubArray(vector<int>& nums) { 
        vector<int> freq(50000, 0); 
        int max_ = 0; 
        for (const int n : nums) 
            max_ = max(max_, ++freq[n]); 
        fill(freq.begin(), freq.end(), 0); 
        int min_ = nums.size(); 
        for (int i = 0, j = -1, size = nums.size(); j < size;) { 
            if (j >= 0 && freq[nums[j]] == max_) 
                min_ = min(min_, j - i + 1), --freq[nums[i++]]; 
            else if (j < size - 1) 
                ++freq[nums[++j]]; 
            else 
                break; 
        } 
        return min_; 
    } 
}; 
int main(){ 
    Solution ob; 
    vector<int> v = {1, 2, 2, 3, 1}; 
    cout << (ob.findShortestSubArray(v)); 
}

इनपुट

{1, 2, 2, 3, 1}