python(leetcode)-重覆元素演算法題

leetcode初級演算法 

問題描述

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

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

該問題表述非常簡單 查看數組中是否有相同元素

解法一：（未通過-超出時間限制)

思路：利用list的內置函數count計算每一個元素的數量 如果出現大於1則return True  如果都等於1 return False

 1 class Solution:
 2     def containsDuplicate(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: bool
 6         """
 7         count=0
 8         if(len(nums)==0):
 9             return False
10         else:
11             for i in nums:
12                 if(nums.count(i)!=1):
13                     return True
14             return False
15 if __name__=="__main__":
16     s=Solution()
17     li=[2,4,6,5]
18     print(s.containsDuplicate(li))

分析原因：內置函數list.count(i)時間複雜度為O(n) 外面嵌套一層迴圈 總的時間為O（n^2)

解法二（通過）

思路 首先利用內置函數sort()將list排序  然後對每兩個相鄰位置進行判斷是否相等 如果有相同則return True 否則return False

 1 class Solution:
 2     def containsDuplicate2(self,nums):
 3         nums.sort()
 4         if (len(nums) == 0):
 5             return False
 6         else:
 7             for i in range(len(nums)-1):
 8                 left=nums[i+1]
 9                 right=nums[i]
10                 result=left==right
11                 if(result):
12                     return True
13             return False
14 if __name__=="__main__":
15     s=Solution()
16     li=[2,4,6,5]
17     print(s.containsDuplicate2(li))

解法三（通過）

思路：利用set()的特性不存在重覆元素  然後判斷set的長度和list的長度

 1 class Solution:
 2     def containsDuplicate(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: bool
 6         """
 7         set1 = set(nums)
 8         if len(set1) == len(nums):
 9             return False
10         else:
11             return True
12 if __name__=="__main__":
13     s=Solution()
14     li=[2,4,6,5]
15     print(s.containsDuplicate2(li))