C++ এ একটি অ্যারের ডিগ্রি

ধরুন আমাদের কাছে একটি অ-ঋণাত্মক পূর্ণসংখ্যার অ্যারে আছে যাকে 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 আকারের একটি অ্যারের ফ্রিকোয়েন্সি সংজ্ঞায়িত করুন এবং এটি 0 দিয়ে পূরণ করুন
• সর্বোচ্চ_ :=0
• সংখ্যায় প্রতিটি n এর জন্য
  • (1 দ্বারা ফ্রিকোয়েন্সি [n] বাড়ান)
  • max_ :=max_ এবং freq[n]
  এর সর্বোচ্চ
• 0 দিয়ে freq অ্যারে পূরণ করুন।
• min_ :=সংখ্যার আকার
• আরম্ভ করার জন্য i :=0, j :=-1, size :=সংখ্যার আকার, যখন j
• যদি j>=0 এবং freq[nums[j]] max_ এর সমান হয়, তাহলে −
  • min_ :=সর্বনিম্ন min_ এবং j - i + 1
• অন্যথায় যখন j <আকার - 1, তারপর −
  • j 1 দ্বারা বাড়ান
  • 1 দ্বারা ফ্রিকোয়েন্সি [সংখ্যা[j]] বাড়ান
• অন্যথায়
  • লুপ থেকে বেরিয়ে আসুন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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