题解 | 小红的不动点

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

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    unordered_map<int, int> freq;
    for (int i = 0; i < n; ++i) {
        freq[a[i]]++;
    }

    int count = 0;
    for (int i = 0; i < n; ++i) {
        if (freq[a[i]] == a[i]) {
            count++;
        }
    }

    cout << count << endl;

    return 0;
}

程序使用哈希表（unordered_map）计算数组中“不动点”的数量，“不动点”定义为元素值等于其在数组中出现次数的元素。

时间复杂度为 O(n) O(n) O(n)（哈希表操作平均为 O(1) ，空间复杂度为 O(n) 用于存储哈希表和数组。