217. 存在重复元素
思路
首先,要确定一个元素是否出现多次,那么肯定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
}
Python解法 set
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return not len(nums) == len(set(nums))
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
有疑问加站长微信联系(非本文作者)