C++中查找数组相等值的方法及高效实现问询

嘿，咱们先从你的现有代码说起——首先得提个小bug：你内层循环里的自增变量写错啦！for(int k = i; k < arrayLenght; i ++)这里应该是k++，不然i会被内外层循环同时递增，逻辑完全乱掉。另外arrayLenght拼写也有误，应该是arrayLength。先给你修正后的基础双重循环版本：

for(int i = 0; i < arrayLength; i++) {
    // 从i+1开始，避免和自身对比、重复检查
    for(int k = i + 1; k < arrayLength; k++) {
        if(array[i] == array[k]) {
            char message[100];
            sprintf(message,"There is a duplicate of %s", array[i]);
            ShowMessage(message);
            break;
        }
    }
}

（如果你的数组不是字符串类型，记得调整sprintf的格式符哦）

当然，双重循环的时间复杂度是O(n²)，当数组元素数量较多时会很慢，这里有两种更高效的优化方案：

方法一：排序后遍历检查 #

思路是先对数组排序（时间复杂度O(n log n)），排序后重复元素会相邻，之后只需一次遍历（O(n)）就能找到重复项，整体时间复杂度远低于O(n²)。

代码示例（假设数组是std::string类型）：

#include <algorithm>
#include <string>

std::string array[] = {"a", "b", "c", "a", "d"};
int arrayLength = sizeof(array) / sizeof(array[0]);

// 先排序，会改变原数组顺序，需要保留原数组的话先复制一份
std::sort(array, array + arrayLength);

// 遍历找相邻重复元素
for(int i = 1; i < arrayLength; i++) {
    if(array[i] == array[i-1]) {
        char message[100];
        sprintf(message,"There is a duplicate of %s", array[i].c_str());
        ShowMessage(message);
        // 找第一个重复就break，找所有重复就去掉break
        break;
    }
}

方法二：使用哈希表（std::unordered_set） #

利用std::unordered_set不允许存储重复元素的特性，遍历数组时尝试插入元素：如果插入失败，说明该元素已经存在，也就是找到了重复值。平均时间复杂度是O(n)，是效率最高的方案之一。

代码示例：

#include <unordered_set>
#include <string>

std::string array[] = {"a", "b", "c", "a", "d"};
int arrayLength = sizeof(array) / sizeof(array[0]);

std::unordered_set<std::string> seen;

for(int i = 0; i < arrayLength; i++) {
    // insert返回的pair中，second为false表示元素已存在
    if(!seen.insert(array[i]).second) {
        char message[100];
        sprintf(message,"There is a duplicate of %s", array[i].c_str());
        ShowMessage(message);
        break;
    }
}

这个方法不会改变原数组顺序，唯一的小代价是需要额外的存储空间（空间复杂度O(n)），但大多数情况下这个取舍是完全值得的。

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