LeetCode如何统计数组中每个数的出现次数

# LeetCode如何统计数组中每个数的出现次数

在算法面试和编程竞赛中，统计数组中元素的出现频率是常见的基础操作。本文将详细介绍多种实现方法，并通过LeetCode真题演示具体应用场景。

## 一、问题定义与基础解法

### 1.1 问题描述
给定一个整数数组`nums`，需要统计每个数字出现的次数，并返回统计结果。

示例：
```python
输入: nums = [1,2,3,2,1,4]
输出: {1:2, 2:2, 3:1, 4:1}

1.2 基础实现方法

方法一：暴力枚举（不推荐）

时间复杂度：O(n²)

def count_occurrences(nums):
    count_dict = {}
    for num in nums:
        if num not in count_dict:
            count_dict[num] = nums.count(num)
    return count_dict

方法二：哈希表标准解法

时间复杂度：O(n)

def count_occurrences(nums):
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    return freq

二、进阶方法与优化技巧

2.1 使用collections模块

Python标准库提供了更简洁的实现方式：

from collections import defaultdict, Counter

# 使用defaultdict
def count_with_defaultdict(nums):
    freq = defaultdict(int)
    for num in nums:
        freq[num] += 1
    return dict(freq)

# 使用Counter（推荐）
def count_with_counter(nums):
    return dict(Counter(nums))

2.2 Java实现示例

import java.util.HashMap;

public Map<Integer, Integer> countOccurrences(int[] nums) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }
    return freq;
}

三、LeetCode实战应用

3.1 经典题目：两数之和（#1）

虽然直接使用频率统计不是最优解，但可以扩展思路：

def twoSum(nums, target):
    freq = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in freq:
            return [freq[complement], i]
        freq[num] = i

3.2 高频元素问题（#347）

def topKFrequent(nums, k):
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)

3.3 存在重复元素（#217）

def containsDuplicate(nums):
    return len(nums) != len(set(nums))
    # 或使用频率统计
    # return any(v > 1 for v in Counter(nums).values())

四、特殊场景处理

4.1 大整数处理

当数字范围很大但稀疏时，建议： 1. 使用更高效的数据结构（如Trie） 2. 考虑位图法（BitMap）

4.2 流式数据处理

对于无法完全加载到内存的大数据：

from collections import defaultdict

def count_stream(stream):
    freq = defaultdict(int)
    for num in stream:
        freq[num] += 1
        # 可以定期写入磁盘
    return freq

五、算法复杂度分析

六、扩展思考

6.1 并行统计方案

对于超大规模数据，可采用MapReduce模型：

# Map阶段
def mapper(num):
    return (num, 1)

# Reduce阶段
def reducer(pairs):
    return (pairs[0], sum(pairs[1]))

6.2 概率统计方法

当允许近似统计时： - HyperLogLog：基数估计 - Count-Min Sketch：频率估计

七、最佳实践建议

1. 常规场景：优先使用collections.Counter
2. 内存敏感：考虑使用数组代替哈希表（当数据范围已知）
3. 多语言实现：
   • C++：std::unordered_map
   • JavaScript：Map对象
4. 测试边界条件：
   • 空数组
   • 超大数值
   • 浮点数情况

八、总结

掌握元素频率统计是算法基础中的关键技能。通过本文介绍的： - 标准哈希表实现 - 语言特性优化 - 实际应用案例 - 特殊场景处理

读者可以应对LeetCode中80%以上的频率统计相关问题。建议结合具体题目（如#242有效字母异位词、#438找到字符串中所有字母异位词）进行强化练习。

附录：相关LeetCode题目列表 - #1 两数之和 - #217 存在重复元素 - #347 前K个高频元素 - #451 根据字符出现频率排序 - #692 前K个高频单词 “`

这篇文章共计约1500字，采用Markdown格式编写，包含代码示例、复杂度分析和实战应用。可根据需要调整具体细节或补充更多语言实现。