面试题：Rust 中统计功能原子实现基础复杂度分析

Question

假设你要在 Rust 中实现一个简单的统计功能，用于统计一个整数数组中每个数字出现的次数。请使用原子操作实现该功能，并简要分析此实现的时间和空间复杂度。

Answer 1

use std::sync::{Arc, atomic::{AtomicUsize, Ordering}};
use std::collections::HashMap;

fn count_numbers(arr: &[i32]) -> HashMap<i32, Arc<AtomicUsize>> {
    let mut result = HashMap::new();
    for &num in arr {
        let count = result.entry(num).or_insert_with(|| Arc::new(AtomicUsize::new(0)));
        count.fetch_add(1, Ordering::SeqCst);
    }
    result
}

时间复杂度分析

1. 遍历数组：代码通过 for 循环遍历输入数组 arr 一次，每次遍历执行的操作时间复杂度为常数级（O(1)），因此遍历数组的时间复杂度为 O(n)，其中 n 是数组的长度。
2. HashMap 操作：entry 方法用于获取或插入键值对，平均时间复杂度为 O(1)，fetch_add 操作的时间复杂度也是常数级 O(1)。由于这两个操作都在循环内部执行，总的时间复杂度仍然是 O(n)。

空间复杂度分析

1. HashMap：HashMap 用于存储每个数字及其出现次数，最坏情况下，所有数字都不相同，HashMap 会存储 n 个键值对，空间复杂度为 O(n)。
2. 原子操作：每个 AtomicUsize 占用固定大小的空间，总的空间复杂度也为 O(n)。

综上，时间复杂度为 O(n)，空间复杂度为 O(n)。