Contains Duplicate

image.png

[圖片上傳中...(image.png-d0fb52-1516785963782-0)]

利用set不能保存重復(fù)元素的特性，判斷前后兩個數(shù)組長度是否相同即可：

題目翻譯

給定一個整數(shù)數(shù)組，判斷其中是否包含重復(fù)元素。你要寫的函數(shù)，當(dāng)包含重復(fù)元素時返回 true，否則返回 false。

思路方法

首先我們可能會想到，遍歷數(shù)組，對于每個元素，再檢查后面所有元素是否有相同的就可以了。然而這樣時間復(fù)雜度太高，會超時，所以不可取。

思路一

既然暴力查重不可取，那么我沒先將數(shù)組進行排序（排序的復(fù)雜度），排序后比較每個元素與后一個元素是否相等即可。

代碼

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        nums.sort()
        for i in xrange(0, len(nums)-1):
            if nums[i] == nums[i+1]:
                return True
        return False

思路二

通過字典（HashMap），將出現(xiàn)過的數(shù)記錄下來，遍歷下一個數(shù)時檢查是否已經(jīng)出現(xiàn)過。

代碼

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        map = {}
        for i in nums:
            if i in map:
                return True
            map[i] = True
        return False

思路三

沒有重復(fù)的數(shù)組相當(dāng)于集合，利用Python的set，將數(shù)組轉(zhuǎn)換成集合，若長度與原來相等則說明沒有重復(fù)。

代碼

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        return len(nums) != len(set(nums))