c++如何判断数组中是否有重复元素_c++使用set查重【技巧】-C++

用std::unordered_set判断重复最高效，平均o(1)插入，内置类型无需额外配置；std::set次之，o(log n)；排序扫描o(n log n)但省空间；避免o(n²)的count或嵌套循环。

用 std::set 判断数组是否有重复元素最简单

直接把所有元素插入 std::set，利用其自动去重特性：插入时如果元素已存在，insert() 返回的 pair<bool iterator>::first</bool> 为 false，遇到第一个 false 就能立刻返回 true（表示有重复）。

注意别用 std::set::size() 对比原数组长度——这要等全部插入完，浪费时间且无法提前退出。

bool hasDuplicate(const std::vector<int>& arr) {
    std::set<int> seen;
    for (int x : arr) {
        if (!seen.insert(x).second) {
            return true; // 插入失败，说明已存在
        }
    }
    return false;
}

想更快？改用 std::unordered_set

std::set 是红黑树，单次插入平均 O(log n)；std::unordered_set 是哈希表，平均 O(1)，整体更优，尤其数据量大时。

但要注意：自定义类型作 key 时，必须提供 hash 和 operator==；内置类型（如 int、std::string）可直接用。

立即学习“C++免费学习笔记（深入）”；

• 空间换时间：哈希表可能有额外内存开销和哈希冲突
• 不保证顺序，但查重不需要顺序
• 最坏情况（大量哈希冲突）退化成 O(n) 插入，但实践中极少发生

原地排序后扫描也能做，但会破坏原始顺序

对数组排序后，相邻相等即说明重复。时间复杂度 O(n log n)，空间 O(1)（若允许修改原数组）。