python(leetcode)-重复元素算法题
程序员文章站
2022-05-14 09:50:08
leetcode初级算法 问题描述 给定一个整数数组,判断是否存在重复元素。 如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。 该问题表述非常简单 查看数组中是否有相同元素 解法一:(未通过-超出时间限制) 思路:利用list的内置函数count计 ......
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))