如何高效查找用户输入数组中的重复元素？

我需要查找用户输入到数组中的重复元素，尝试用for循环检测但没成功，求高效实现方案。当前使用的C++代码如下：

#include <iostream>
#include <algorithm>

int main()
{
    int size, * array; 
    std::cout << "Indtast arrayet's stoerrelse." << std::endl;
    std::cin >> size; // 接收用户输入的数组大小
    array = new int[size]; // 动态分配数组

    while (size >= 100) { // 判断数组大小是否过大
        std::cout << "Forkert input af array." << std::endl;
        break;
    }

    while (size <= 100) { // 数组大小符合要求时执行

        float sum = 0;
        float gns = 0;

        std::cout << "Tast op til " << size << " vaerdier ind." << std::endl; 

        for (int i = 0; i < size; i++) { // 接收每个数组元素的输入
            std::cout << "Indtast vaerdi for array-nr: " << i << std::endl;
            std::cin >> array[i]; // 输入元素值

            sum += array[i]; // 计算数组元素总和
        }
        std::cout << "Min-vaerdi er: " << *std::min_element(array, array + size) << std::endl;
        std::cout << "Max-vaerdi er: " << *std::max_element(array, array + size) << std::endl;
        std::cout << "Summen er: " << sum << std::endl;
        gns = sum / size; // 计算平均值
        std::cout << "Gennemsnittet er: " << gns << std::endl;


        return 0;
    }
}

两种高效检测重复元素的方案 #

方案1：排序后遍历检测（时间复杂度O(n log n)）

先对数组排序，重复元素会自动相邻，遍历数组时只需比较当前元素与下一个元素是否相等即可。该方案无需额外容器，内存占用低。

将以下代码插入到原代码计算平均值之后：

// 排序数组
std::sort(array, array + size);
std::cout << "重复元素：";
bool hasDuplicate = false;
for (int i = 0; i < size - 1; i++) {
    if (array[i] == array[i+1]) {
        // 避免重复输出同一组重复元素
        if (i == 0 || array[i] != array[i-1]) {
            std::cout << array[i] << " ";
            hasDuplicate = true;
        }
    }
}
if (!hasDuplicate) {
    std::cout << "无";
}
std::cout << std::endl;

方案2：哈希表（unordered_set）检测（时间复杂度O(n)）

利用unordered_set的元素唯一性特性，遍历数组时尝试将元素插入集合，若插入失败则说明该元素已存在（即重复）。该方案时间效率更高，适合大数据量场景。

首先添加头文件#include <unordered_set>，再将以下代码插入到原代码计算平均值之后：

std::unordered_set<int> seen;
std::cout << "重复元素：";
bool hasDuplicate = false;
for (int i = 0; i < size; i++) {
    auto result = seen.insert(array[i]);
    if (!result.second) {
        // 仅在第一次发现重复时输出
        if (seen.count(array[i]) == 1) {
            std::cout << array[i] << " ";
            hasDuplicate = true;
        }
    }
}
if (!hasDuplicate) {
    std::cout << "无";
}
std::cout << std::endl;

原代码逻辑修正提示 #

原代码的两个while循环存在逻辑漏洞：当输入的size >=100时，输出错误后break，但程序不会释放动态数组，会造成内存泄漏；且第二个while循环完全没必要，因为size是固定值，改用if判断更合理。修正示例：

if (size >= 100) {
    std::cout << "Forkert input af array." << std::endl;
    return 0; // 直接退出程序
}
// 去掉第二个while循环，直接执行后续逻辑

// 程序结束前释放动态数组
delete[] array;

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