如何检查数组是否有重复项？

如何检查数组是否有重复项

基础概念

检查数组是否有重复项是编程中常见的操作，指的是判断一个数组中是否存在两个或更多相同的元素。这在数据处理、输入验证和算法设计中都非常有用。

方法比较

1. 使用Set数据结构（推荐方法）

原理：利用Set自动去重的特性，比较原始数组长度和Set化后的长度。

优势：

代码简洁
时间复杂度O(n)
适用于大多数现代编程语言

示例代码：

function hasDuplicate(arr) {
    return new Set(arr).size !== arr.length;
}

// 使用示例
console.log(hasDuplicate([1, 2, 3, 1])); // true
console.log(hasDuplicate([1, 2, 3]));    // false

2. 使用哈希表/对象

原理：遍历数组并使用哈希表记录已出现的元素。

优势：

可以提前终止（发现重复立即返回）
时间复杂度O(n)

示例代码：

function hasDuplicate(arr) {
    const seen = {};
    for (let item of arr) {
        if (seen[item]) return true;
        seen[item] = true;
    }
    return false;
}

3. 双重循环

原理：对每个元素检查其后是否有相同元素。

劣势：

时间复杂度O(n²)
效率低，不推荐用于大型数组

示例代码：

function hasDuplicate(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] === arr[j]) return true;
        }
    }
    return false;
}

4. 排序后检查相邻元素

原理：先排序数组，然后检查相邻元素是否相同。

优势：

空间复杂度O(1)（如果允许修改原数组）

劣势：

时间复杂度取决于排序算法（通常O(n log n)）

示例代码：

function hasDuplicate(arr) {
    const sorted = [...arr].sort();
    for (let i = 1; i < sorted.length; i++) {
        if (sorted[i] === sorted[i - 1]) return true;
    }
    return false;
}

应用场景

表单验证：检查用户输入是否有重复值
数据处理：确保数据集的唯一性
算法优化：某些算法要求输入数据无重复
缓存管理：避免重复缓存相同内容

注意事项

对象/引用类型比较：上述方法对于对象/数组等引用类型可能不适用，需要自定义比较函数
NaN处理：JavaScript中Set可以正确处理NaN，但其他方法可能需要特殊处理
性能考虑：根据数组大小选择合适的方法

各语言实现示例

Python

def has_duplicate(arr):
    return len(arr) != len(set(arr))

Java

import java.util.HashSet;
import java.util.Set;

public boolean hasDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (set.contains(num)) return true;
        set.add(num);
    }
    return false;
}

C++

#include <unordered_set>
#include <vector>

bool hasDuplicate(const std::vector<int>& nums) {
    std::unordered_set<int> seen;
    for (int num : nums) {
        if (seen.count(num)) return true;
        seen.insert(num);
    }
    return false;
}

选择哪种方法取决于具体需求、编程语言和性能要求。对于大多数现代应用，使用Set/哈希表的方法是最优选择。