判斷數組中是否存在重複元素

數組

• 數組
• • python的使用方法
  • • 給定一個整數數組，判斷是否存在重複元素。

數組

原理

python的使用方法

清單中元素的排列

sort方法

給定一個整數數組，判斷是否存在重複元素。

如果存在一值在數組中出現至少兩次，函數傳回 true 。如果數組中每個元素都不相同，則傳回 false 。

解題思路

1. 對現有數組進行排序，
2. 對數組中的元素進行按位比較

#第一版代碼：
class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        #1. 對清單中的元素進行排序
        nums.sort()
        print "nums", nums
        n = len(nums)
        print n
        i = 0
        # while i <= n:
        #     if nums[i] == nums[i+1]:
        #         return True
        #     else:
        #         return False
        for i in range(n-1):
            if nums[i] == nums[i+1]:
                return True
            else:
                return False
            i = i + 1
           

報錯資訊如上：循環變量設定錯誤，循環變量的值始終為0，目前兩位元素相同時，可傳回為true，當清單中隻有一個元素中，無法進行輸出，

修改後的代碼如下：

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

循環變量設定有誤，i的值始終為0，此時元素無法移位進行比較，隻會比較第一和第二位，不會比較到後兩位元素

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

目前的 時間複雜度為：O(nlogn),空間複雜度為1

解法二：

哈希表

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        #方法二：哈希表
        visted = set()
        for num in nums:
            if num in visted:
                return True
            visted.add(num)
        return False
           

時間複雜度：O(N),空間複雜度O(N)

個人見解：以空間換時間的方式進行