在数组中查找所有重复元素 (C++)

Source: Dev.to

问题概述

找出数组中出现多次的所有元素，并且每个重复元素只报告一次。

示例

Input:  [1, 2, 3, 2, 4, 1]
Output: [1, 2]

方法一：频率数组

当可能取值的范围已知且相对较小时使用此方法。

#include 
using namespace std;

int main() {
    vector n = {1, 2, 3, 2, 4, 1};
    vector out;
    vector tracker(100, 0);   // 根据取值范围调整大小

    for (int x : n) tracker[x]++;

    for (size_t i = 0; i  1) {
            out.push_back(static_cast(i));
        }
    }
    // `out` now contains the duplicate values
}

复杂度

• 时间： O(n + k) 其中 n 为元素个数，k 为取值范围的大小。
• 空间： O(k) 用于频率数组。

何时使用

• 取值范围已知且较小，能够使用紧凑的频率数组。
• 需要尽可能快的查找速度。

方法二：使用 unordered_map

此方法适用于任意取值范围。

#include 
#include 
using namespace std;

int main() {
    vector n = {1, 2, 3, 2, 4, 1};
    vector out;
    unordered_map tracker;

    for (int x : n) tracker[x]++;

    for (const auto& it : tracker) {
        if (it.second > 1) {
            out.push_back(it.first);
        }
    }
    // `out` now contains the duplicate values
}

复杂度

• 时间： 平均 O(n)（哈希表操作）。
• 空间： O(n + z) 其中 z 为不同重复值的数量。

何时使用

• 可能的取值范围未知或很大。
• 需要一个能够适应任何输入域的灵活方案。

关键对比

最终要点

两种方法都能正确识别重复元素。
当取值范围受限且需要最高速度时，选择频率数组方法。
当取值范围未知或较大时，选择 unordered_map 方法，接受适度增加的空间开销。

理解 为什么 选择某种方法往往比代码本身更重要。