python(leetcode)-重复元素算法题

2019-02-25 16:13:50来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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))

 


原文链接:https://www.cnblogs.com/bob-jianfeng/p/10359327.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:python3 str各个功能记录

下一篇:python 获取excel数据 自动登陆