存在重复元素

发表于 分类于 阅读次数：

存在重复元素（难度：简单）

1

方法一：哈希表

复杂度

时间复杂度 : O(n)。search() 和 insert() 各自使用 n 次，每个操作耗费常数时间。

空间复杂度 : O(n)。哈希表占用的空间与元素数量是线性关系。

代码
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> res = new HashSet<>();
        for(int num:nums){
            if(res.contains(num))
                return true;
            res.add(num);
        }
        return false;
    }
}
3

另一种思路：利用Python中的set()，判断所得结果长度与原数组长度的关系

1
2
3
4
5
6
7
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        set1 = set(nums)
        if len(set1) == len(nums):
            return False
        else:
            return True
2

方法二： 排序

如果存在重复元素，排序后它们应该相邻。

复杂度

时间复杂度 : O(nlogn)。

空间复杂度 : O(1)。这取决于具体的排序算法实现，通常而言，使用 堆排序 的话，是 O(1)。

代码
1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0; i < nums.length-1; i++){
            if(nums[i]==nums[i+1])
                return true;
        }
        return false;
    }
}
4

注：对于一些特定的 n不太大的测试样例，方法一的运行速度可能会比方法二更慢。这是因为哈希表在维护其属性时有一些开销。要注意，程序的实际运行表现和 Big-O 符号表示可能有所不同。Big-O 只是告诉我们在 充分大的输入下，算法的相对快慢。因此，在 n不够大的情况下， O(n)的算法也可以比 O(nlogn)的更慢。