217. Contains Duplicate

217. Contains Duplicate

题目:
https://leetcode.com/problems/contains-duplicate/

难度:

Easy

我直接sort,然后比较相邻的元素,这样O(n),也是笨办法,居然unlocked a solution,所以来读读解答.

三个办法:

  • linear search O(n^2)
  • sort O(n)
  • hashtable

我用的sort

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

看给的Java解法

public boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<>(nums.length);
    for (int x: nums) {
        if (set.contains(x)) return true;
        set.add(x);
    }
    return false;
}

还有一个取巧的Python解法,我也看到了

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

推荐阅读更多精彩内容