問題描述

你得到一個長度為 $n$ 的整數陣列

從左到右計算每個長度為 $k$ 的視窗的眾數並輸出

練習題

連結：https://cses.fi/problemset/task/3224

完整程式碼

#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;

    unordered_map<int, int> freq; // 數字出現次數
    map<int, set<int>> freq_map;  // 頻率 -> 數字集合（有序）
    int max_freq = 0;

    // 初始化前 k 個元素
    for (int i = 0; i < k; ++i) {
        int x = a[i];
        int f = freq[x]++;
        if (f > 0) {
            freq_map[f].erase(x);
            if (freq_map[f].empty()) freq_map.erase(f);
        }
        freq_map[f + 1].insert(x);
        max_freq = max(max_freq, f + 1);
    }

    // 輸出第一個視窗的眾數
    cout << *freq_map[max_freq].begin();

    // 處理剩下的視窗
    for (int i = k; i < n; ++i) {
        int out = a[i - k];
        int in = a[i];

        // 移除視窗外的元素
        int f_out = freq[out]--;
        freq_map[f_out].erase(out);
        if (freq_map[f_out].empty()) freq_map.erase(f_out);
        if (freq[out] > 0)
            freq_map[f_out - 1].insert(out);
        else
            freq.erase(out); // 出現次數歸 0 就移除

        // 加入視窗內的新元素
        int f_in = freq[in]++;
        if (f_in > 0) {
            freq_map[f_in].erase(in);
            if (freq_map[f_in].empty()) freq_map.erase(f_in);
        }
        freq_map[f_in + 1].insert(in);

        // 更新 max_freq
        if (!freq_map.count(max_freq)) max_freq--; // 原本的 max_freq 可能被移光
        if (f_in + 1 > max_freq) max_freq = f_in + 1;

        cout << " " << *freq_map[max_freq].begin();
    }

    cout << endl;
    return 0;
}