[LeetCode] 217.Contains-Duplicate | 数组包含相同元素判断

题目来源：LeetCode: 217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

思路

  • 冒泡的方式逐一比较, 时间复杂度: O(n^2)
  • 先折半插入排序, 过程中比较是否有相同元素, 时间复杂度：O(nlogn)
  • 逐一将元素插入Set或HashTable，判断是否已重复, 时间复杂度: O(n)

源码1：将元素逐一加入Set集合中，判断是否已存在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """

        if len(nums) == 0:
            return False
        from sets import Set
        record = Set()
        for num in nums:
            if num in record:
                return True
            else:
                record.add(num)
        return False

运行结果：

16 / 16 test cases passed.
Status: Accepted
Runtime: 80 ms
Submitted: 0 minutes ago

You are here! Your runtime beats 2.85% of csubmissions.

源码2：元素加入集合，判断集合长度和源数据列表长度是否一致

1
2
3
4
5
6
7
8
class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        from sets import Set
        return len(nums)!=len(Set(nums))

运行结果：

16 / 16 test cases passed.
Status: Accepted
Runtime: 52 ms
Submitted: 0 minutes ago

You are here! Your runtime beats 57.23% of csubmissions.

总结

  1. Python中Set in 方法会导致算法效率下降为O(nlogn)
  2. 增加Set或HashTable已存在元素时的处理，可将算法优化为O(n)
  3. Python中数据类型的函数功能可快速实现算法问题，但要注意其可解决问题，但非完美解决方案，很大程度受Python内置函数实现原理的影响。