云野 ☁️

3.存在重复元素

|
|
访问
本文共457字。
展开

题目描述

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]
输出：true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/contains-duplicate

方法1、排序

执行用时：88 ms

时间复杂度：O(nlogn)

空间复杂度：O(logn)

思路总结：先排序，遍历每个数，判断相邻的数是否相同。有相同，返回true；无，返回false。

注意：for循环要执行完毕，才能return false。

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        list.sort(nums)
        for i in range(len(nums)-1):
            if nums[i]==nums[i+1]:
                return True
        return False # 这里我犯错了

方法2、集合Set

执行用时：48 ms

时间复杂度：O()

空间复杂度：O()

思路总结：利用set集合的不重复性，将数组转set，如果长度不一致，说明有重复的元素。

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        # return not len(set(nums))==len(nums) # 一行解决 40ms
        s = set(nums)
        if len(s) == len(nums):
            return False
        return True

也可以遍历数组，逐个存入空集合，如果已存在，表示有重复。32ms

同理，也可以构建一个hash表。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        s = set()
        for i in nums:
            if i in s:
                return True
            else:
                s.add(i)
        return False

方法3、哈希表

执行用时： ms

时间复杂度：O()

空间复杂度：O()

思路总结：新建一个hash表，遍历数组，if hash表里存在相同的数，return True。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        hashtable = dict()
        for i in nums:
            if i in hashtable:
                return True
            else:
                hashtable[i]=1  # 随便赋一个值
        return False