C++-এ অ্যারের ডিগ্রি (Degree of an Array)

নন-নেগেটিভ পূর্ণসংখ্যার একটি অ্যারে nums দেওয়া আছে। এই অ্যারের ডিগ্রি হল এর যেকোনো একটি উপাদানের সর্বোচ্চ ফ্রিকোয়েন্সি। আমাদের nums-এর সবচেয়ে ছোট সংলগ্ন সাবঅ্যারে খুঁজে বের করতে হবে যের ডিগ্রি nums-এর ডিগ্রির সমান।

ইনপুট [1,2,2,3,1] হলে আউটপুট ২। কারণ অ্যারেটির ডিগ্রি ২ (১ এবং ২ দুবার আসে)। ডিগ্রি ২ যেগুলো সাবঅ্যারে: [1,2,2,3,1], [1,2,2,3], [2,2,3,1], [1,2,2], [2,2,3], [2,2]। সবচেয়ে ছোট দৈর্ঘ্য ২।

সমাধানের ধাপসমূহ

ফ্রিকোয়েন্সি অ্যারে freq (আকার ৫০০০০) ০ দিয়ে ভরুন
max_ := 0
প্রতিটি n ∈ nums এর জন্য freq[n]++, max_ := max(max_, freq[n])
freq আবার ০ দিয়ে ভরুন
min_ := nums.size()
স্লাইডিং উইন্ডো (i, j) ব্যবহার করে ন্যূনতম দৈর্ঘ্যের সাবঅ্যারে খুঁজুন যেটির ডিগ্রি max_
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}