本文介绍如何在 o(n) 时间复杂度内统计数组中各元素的出现频次，并仅输出频次大于 1 的元素及其计数，适用于面试与高性能场景。
本文介绍如何在 o(n) 时间复杂度内统计数组中各元素的出现频次，并仅输出频次大于 1 的元素及其计数，适用于面试与高性能场景。
在实际开发和算法面试中，常需对数组进行频次分析（frequency counting），例如识别重复元素、去重、或统计热门项。关键约束是时间复杂度必须为 O(n) ——即仅允许单轮遍历或常数轮遍历，不可使用嵌套循环（O(n²)）或未优化的 filter + indexOf 等方案。
✅ 核心思路：哈希表（Object / Map）一次计数 + 一次过滤
我们利用 JavaScript 中对象（或 Map）的键值对特性，以元素值为键、出现次数为值，在 第一轮遍历中完成频次统计；随后遍历该哈希表，筛选并打印 count > 1 的条目。两轮遍历均为 O(n)，整体仍为 O(n)。
以下是推荐实现（使用普通对象，简洁且兼容性好）：
function countAndPrintDuplicates(arr) {
const freq = {}; // 频次哈希表：{ element: count }
// 第一轮：O(n) —— 统计每个元素出现次数
for (const item of arr) {
freq[item] = (freq[item] || 0) + 1;
}
// 第二轮：O(k)，k 为唯一元素个数 ≤ n → 整体仍为 O(n)
for (const key in freq) {
if (freq[key] > 1) {
console.log(`${key}: ${freq[key]}`);
}
}
}
// 示例调用
countAndPrintDuplicates([1, 3, 6, 1, 4, 7, 1, 3]);
// 输出：
// 1: 3
// 3: 2? 提示：freq[item] = (freq[item] || 0) + 1 是安全初始化的经典写法，避免 undefined + 1 导致 NaN。
立即学习“Java免费学习笔记（深入）”；
? 进阶优化建议（可选）
-
使用 Map 替代普通对象：当数组含非字符串类型（如对象、null、Symbol）或需严格类型区分时，Map 更可靠（Object 会将所有键转为字符串）：
const freq = new Map(); for (const item of arr) { freq.set(item, (freq.get(item) || 0) + 1); } for (const [key, count] of freq) { if (count > 1) console.log(`${key}: ${count}`); } -
返回结果而非打印：便于测试与复用：
return Object.entries(freq) .filter(([, count]) => count > 1) .map(([val, count]) => ({ value: val, count })); // → [{ value: "1", count: 3 }, { value: "3", count: 2 }]
⚠️ 注意事项
- 类型隐式转换风险：[1, '1'] 在普通对象中会被视为同一键（因 obj['1'] === obj[1]）。若需区分数字 1 和字符串 '1'，务必使用 Map。
- 稀疏数组/空值处理：本方案天然支持 null、undefined（作为独立键），但 undefined 作键时需注意 Map 允许，而对象中 obj[undefined] 实际等价于 obj['undefined']。
- 空间复杂度为 O(k)：k 为唯一元素数量，最坏情况 k = n（全不重复），属合理代价。
✅ 总结
该解法以两次线性扫描达成 O(n) 时间复杂度，符合面试高频要求；代码简洁、逻辑清晰、易于理解与扩展。掌握此模式，不仅能解决重复统计问题，也为滑动窗口、子数组计数等进阶题目奠定基础。
