array

Contains Duplicate


image.png

[图片上传中...(image.png-d0fb52-1516785963782-0)]

利用set不能保存重复元素的特性,判断前后两个数组长度是否相同即可:

题目翻译

给定一个整数数组,判断其中是否包含重复元素。你要写的函数,当包含重复元素时返回 true,否则返回 false。

思路方法

首先我们可能会想到,遍历数组,对于每个元素,再检查后面所有元素是否有相同的就可以了。然而这样时间复杂度太高,会超时,所以不可取。

思路一

既然暴力查重不可取,那么我没先将数组进行排序(排序的复杂度),排序后比较每个元素与后一个元素是否相等即可。

代码

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),将出现过的数记录下来,遍历下一个数时检查是否已经出现过。

代码

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

思路三

没有重复的数组相当于集合,利用Python的set,将数组转换成集合,若长度与原来相等则说明没有重复。

代码

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        return len(nums) != len(set(nums))
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1. Two Sum 用hash可以得到O(n)时间的解法,用python中的enumerate函数,可以获得元素...
    Morphiaaa阅读 470评论 0 0
  • 构造函数 Array是JavaScript的内置对象,同时也是一个构造函数,可以用它生成新的数组。 上面代码中,A...
    许先生__阅读 316评论 0 1
  • 构造函数 Array是JavaScript的内置对象,同时也是一个构造函数,可以用它生成新的数组。Array构造函...
    zjh111阅读 794评论 0 0
  • 英文文章来源于:https://github.com/Chalarangelo/30-seconds-of-cod...
    缘自世界阅读 286评论 0 2
  • 语音写作,2015年9月10日 其实在这个时候几乎就已经可以用讯飞输入法来进行思维的总结。也就是说当一个人独处的时...
    剑飞在思考阅读 430评论 0 2