ดีกรีของอาร์เรย์ใน 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

วิธีแก้ปัญหา

1. กำหนดอาร์เรย์ freq ขนาด 50000 และเติมด้วย 0
2. max_ := 0
3. for ทุก n ใน nums:
   • เพิ่ม freq[n] ขึ้น 1
   • max_ := max ของ max_ และ freq[n]
4. เติมอาร์เรย์ freq ด้วย 0 อีกครั้ง
5. min_ := ขนาดของ nums
6. for i := 0, j := -1, size := ขนาดของ nums; j < size; ทำ:
   • ถ้า j >= 0 และ freq[nums[j]] เท่ากับ max_: min_ := min ของ min_ และ j - i + 1; ลด freq[nums[i++]]
   • มิฉะนั้นถ้า j < size - 1: เพิ่ม j ขึ้น 1; เพิ่ม freq[nums[j]] ขึ้น 1
   • มิฉะนั้น: ออกจากลูป
7. คืนค่า min_

ตัวอย่างโค้ด C++

#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}

เอาต์พุต

2