C++使用Set查找数组重复元素的代码优化问题咨询

• 核心判断逻辑完全颠倒：setInt.find(integers[i]) != setInt.end()的含义是当前元素已经在Set中存在，原代码此时反而执行插入操作，不存在时才判定为重复，逻辑完全错误
• 注释内容与逻辑不符：注释写明“如果该数字不在set中，说明它不是重复元素”，但对应判断条件完全写反
• 会重复输出同一重复值：如果某个元素出现3次及以上，会重复多次输出该元素是重复值
• 插入语句写法冗余：setInt.insert({integers[i]})不需要额外加花括号，直接传入数值即可
• 输出格式不规范：多个重复值输出时无分隔、无换行，可读性差
• 性能可优化：std::set底层是红黑树，查找插入时间复杂度为O(logn)，换成std::unordered_set可达到平均O(1)的时间复杂度，效率更高

修正逻辑、优化输出与性能后的代码如下：

#include <iostream>
#include <unordered_set>
using namespace std;

void FindDuplicate(int integers[], int n){
  unordered_set<int> existed;
  unordered_set<int> duplicated; // 存储已输出的重复值，避免重复打印

  for(int i = 0; i < n; i++){
    // 元素已存在于已出现集合，判定为重复
    if(existed.count(integers[i])){
      // 仅当该重复值未输出过时打印
      if(!duplicated.count(integers[i])){
        cout << integers[i] << " 是重复元素" << endl;
        duplicated.insert(integers[i]);
      }
    } else {
      // 首次出现的元素存入已出现集合
      existed.insert(integers[i]);
    }
  }
}

int main() {
  int integers [] = {1,2,2,3,3,3,4};
  int n = sizeof(integers)/sizeof(integers[0]);
  FindDuplicate(integers, n);
  return 0;
}

上述代码运行后会输出：

2 是重复元素
3 是重复元素

符合需求，且时间复杂度为O(n)，优于双层for循环的O(n²)方案。

内容的提问来源于stack exchange，提问作者Ope Williams