Bậc của mảng trong C++

Mô tả bài toán

Cho mảng nums các số nguyên không âm. Bậc (degree) của mảng là tần suất lớn nhất của bất kỳ phần tử nào. Tìm độ dài nhỏ nhất của mảng con liên tiếp có bậc bằng bậc của mảng gốc.

Ví dụ: [1,2,2,3,1] → Bậc = 2 (cả 1 và 2 xuất hiện 2 lần). Mảng con ngắn nhất có bậc 2 là [2,2] độ dài 2.

Giải pháp (Cửa sổ trượt + Tần suất)

• Tính tần suất toàn mảng, tìm max_freq.
• Dùng 2 con trỏ i, j duy trì cửa sổ, mảng tần suất trong cửa sổ.
  • Mở rộng j cho đến khi có phần tử đạt tần suất max_freq.
  • Thu hẹp i khi điều kiện thỏa mãn, cập nhật độ dài nhỏ nhất.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        vector<int> freq(50000, 0);
        int max_ = 0;
        for (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);
    return 0;
}

Đầu vào

{1, 2, 2, 3, 1}

Đầu ra

2