小红的不动点

题目描述

对于一个数组，如果一个元素的值等于它在数组中的出现次数，那么称这个元素是"不动点"。给定一个数组，求数组中有多少个不动点。

注意：答案统计的是元素个数而非不同值的个数。例如数组中有 3 个 3，且 3 恰好出现了 3 次，则这 3 个元素都是不动点，贡献 3 而非 1。

思路分析

本题是一道简单的哈希计数模拟题。

1. 统计频次：遍历数组，用哈希表记录每个元素出现的次数。
2. 逐一判定：再次遍历数组，对每个元素 ，若 等于其出现次数 ，则答案加 1。

示例推演

以示例 1 [2, 1, 2, 3, 3, 3] 为例：

所有 6 个元素都是不动点，输出 6。

以示例 2 [1, 2, 3, 1, 2, 3] 为例：

只有值为 2 的 2 个元素是不动点，输出 2。

代码实现

[sol-C++]

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    vector<int> a(n);
    map<int,int> cnt;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        cnt[a[i]]++;
    }
    int ans=0;
    for(int i=0;i<n;i++){
        if(a[i]==cnt[a[i]]) ans++;
    }
    printf("%d\n",ans);
    return 0;
}

[sol-Java]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            cnt.merge(a[i], 1, Integer::sum);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == cnt.get(a[i])) ans++;
        }
        System.out.println(ans);
    }
}

[sol-Python3]

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
print(sum(1 for x in a if x == cnt[x]))

[sol-JavaScript]

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = lines[1].split(' ').map(Number);
    const cnt = {};
    for (const x of a) cnt[x] = (cnt[x] || 0) + 1;
    let ans = 0;
    for (const x of a) if (x === cnt[x]) ans++;
    console.log(ans);
});

复杂度分析

• 时间复杂度：，两次遍历数组，哈希表操作均摊 。
• 空间复杂度：，哈希表存储最多 个不同元素的频次。