JavaScript统计数组元素出现次数并输出次数>1的元素（O(n)复杂度）

核心思路 #

要满足O(n)时间复杂度的要求，最优方案是使用哈希表（字典）完成统计：

• 一次遍历数组，用哈希表记录每个元素的出现次数，时间复杂度O(n)
• 二次遍历哈希表，筛选并输出出现次数大于1的元素，时间复杂度O(n)
  整体操作的时间复杂度为O(n)，空间复杂度为O(n)（最坏情况所有元素唯一）。

代码实现（Python） #

def count_duplicate_elements(arr):
    frequency = {}
    # 统计元素出现频率
    for num in arr:
        frequency[num] = frequency.get(num, 0) + 1
    # 输出符合条件的元素
    for num, cnt in frequency.items():
        if cnt > 1:
            print(f"# {num}: {cnt}")

# 测试输入
input_array = [1, 3, 6, 1, 4, 7, 1, 3]
count_duplicate_elements(input_array)

运行输出 #

1: 3 #

3: 2 #

内容的提问来源于stack exchange，提问作者priya gupta