सी ++ में एक ऐरे की डिग्री

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

इसलिए, यदि इनपुट [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 आकार की एक सरणी आवृत्ति परिभाषित करें और इसे 0 से भरें
• अधिकतम_:=0
• संख्या में प्रत्येक n के लिए
  • (freq[n] 1 से बढ़ाएं)
  • अधिकतम_ :=अधिकतम_ और बारंबारता[n]
• फ़्रीक सरणी को 0 से भरें।
• मिनट_ :=अंकों का आकार
• इनिशियलाइज़ करने के लिए i :=0, j :=-1, size :=nums का आकार, जब j <आकार, करें -
  • यदि j>=0 और freq[nums[j]], max_ के समान है, तो −
    • न्यूनतम_ :=न्यूनतम मिनट_ और j - i + 1
  • अन्यथा जब j <आकार -1, तब −
    • j को 1 से बढ़ाएं
    • फ़्रीक बढ़ाएं[nums[j]] 1 से
  • अन्यथा
    • लूप से बाहर आएं
• वापसी मिनट_

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

उदाहरण

#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_;
   }
};
main(){
   Solution ob;
   vector<int> v = {1, 2, 2, 3, 1};
   cout << (ob.findShortestSubArray(v));
}

इनपुट

{1, 2, 2, 3, 1}

आउटपुट

2