每日一题20201202（217. 存在重复元素）

217. 存在重复元素

image-20201202135946680

思路

首先，要确定一个元素是否出现多次，那么肯定O(n)的复杂度是少不了的，因为肯定需要一次遍历.

一次遍历的话，还需要记住每个数字出现的次数，所以可以考虑用hash表记录数字出现的数字。

看了题解也没有更好的解法了，暴力法更是O(n²)的复杂度，还有一种排序后遍历，复杂度也很高。

golang解法

func containsDuplicate(nums []int) bool {
    hash := make(map[int]int)
    for _, n := range nums {
        hash[n] += 1
        if hash[n] > 1 {
            return true
        }
    }
    return false
}

image-20201202140410924

Python解法 set

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return not len(nums) == len(set(nums))

image-20201202140542147

Python hash表

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        mp = dict()
        for n in nums:
            mp[n] = mp.get(n, 0) + 1
            if mp[n] > 1:
                return True
        return False

image-20201202140749718