题目链接

小红的不动点

题目描述

给定一个数组，我们定义“不动点”为一个特殊的元素，该元素的值恰好等于它在数组中出现的次数。

你需要计算出数组中所有属于“不动点”的元素的总个数。

解题思路

1. 理解问题

首先，我们需要精确理解题意。一个数字 x 是“不动点”，当且仅当 x 的值等于 x 在数组中的出现频率。

通过分析示例可以发现，题目要求的不是有多少个不同种类的不动点，而是所有满足不动点条件的元素的总数量。

例如，在数组 [2, 1, 2, 3, 3, 3] 中：

  • 1 出现了 1 次，值(1) == 频率(1)，所以 1 是不动点。
  • 2 出现了 2 次，值(2) == 频率(2)，所以 2 是不动点。
  • 3 出现了 3 次，值(3) == 频率(3)，所以 3 是不动点。
  • 最终的答案是这些不动点的总个数，即 1 (1的个数) + 2 (2的个数) + 3 (3的个数) = 6。

2. 算法设计

这是一个典型的频率统计问题，使用哈希表（Hash Map）是最高效的解决方案。

  1. 统计频率： 我们遍历一次输入数组，使用一个哈希表来存储每个数字及其出现的次数。哈希表的键（Key）是数组中的数字，值（Value）是该数字的频率。

  2. 寻找不动点并累加： 完成频率统计后，我们遍历哈希表中的每一个键值对 (number, frequency)。

    • 对于每一个键值对，我们检查是否满足 number == frequency 的条件。
    • 如果条件成立，说明 number 是一个不动点。根据题意，我们需要将所有这些不动点元素都计数。该不动点的总个数就是它的频率（也就是它的值），因此我们将这个频率（或值）累加到一个总和变量中。

  3. 得出结果： 遍历完整个哈希表后，累加的总和就是最终的答案。

代码

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    map<int, int> counts;
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        counts[num]++;
    }

    long long fixed_point_total = 0;
    for (auto const& [val, freq] : counts) {
        if (val == freq) {
            fixed_point_total += freq;
        }
    }

    cout << fixed_point_total << endl;

    return 0;
}

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Map<Integer, Integer> counts = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        long fixedPointTotal = 0;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            int val = entry.getKey();
            int freq = entry.getValue();
            if (val == freq) {
                fixedPointTotal += freq;
            }
        }

        System.out.println(fixedPointTotal);
    }
}

import sys
from collections import Counter

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        arr = list(map(int, sys.stdin.readline().split()))
    except (IOError, ValueError):
        return

    counts = Counter(arr)
    
    fixed_point_total = 0
    for val, freq in counts.items():
        if val == freq:
            fixed_point_total += freq
            
    print(fixed_point_total)

solve()

算法及复杂度

  • 算法：哈希表 / 频率统计

  • 时间复杂度：。

    • 遍历数组一次以构建频率哈希表需要 的时间。
    • 遍历哈希表需要的时间与数组中不同元素的数量成正比，在最坏情况下也是 。

  • 空间复杂度：，其中 是数组中不同元素的数量（）。

    • 我们需要一个哈希表来存储每个不同元素的频率。