Leetcode-217的解题过程。

• 题目

  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.

• 解析

  检测给定整数序列中是否有重复元素，这道题可以说是非常基础的问题了，解题的方法也有很多：

  • 1.暴力遍历
    最基本的方法，直接遍历整个序列，在每一步中，用当前元素和前面所有遍历过的元素进行比较，如果有重复直接返回true，遍历完成且没有重复的话就返回false。
    很易于理解的方法，同时也是最笨最慢的方法，不难知道时间复杂度为$O(n^2)$。

    1 2 3 4 5 6 7 8 9 10 11 12 13

    class Solution(object): def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """ seen = [nums[0]] for num in nums[1:]: for seenNum in seen: if seenNum == num: return True seen.append(num) return False

    （如果你真的用这个代码的话，在元素很多的用例中就会TLE）

  • 2.排序后检测
    在数组相关的问题中，将数组排序后再进行其他的处理是一种很常见的做法。在本题中，将数组排序后，如果数组中含有重复的元素，那么它们必定是彼此相邻的，因此，对排序后的数组进行一次遍历即可检测出有无重复元素。这个方法的瓶颈在于排序算法的性能，也就是说时间复杂度至少为$O(n\log{n})$。

    1 2 3 4 5 6 7 8 9 10 11 12 13

    class Solution(object): def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """ nums_sorted = sorted(nums) i=0 for num in nums_sorted[1:]: if num==nums_sorted[i]: return True i+=1 return False

    （Leetcode提交通过，排序偷懒用了python自带的）

  • 3.超级偷懒法
    把list转成set后比较前后的元素个数就可以了。。毫无技术含量

    1 2 3 4 5 6 7 8

    class Solution(object): def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """ numSet = set(nums) return not len(numSet)==len(nums)

    （两行解决，真的偷懒。。）
    python的set内部是使用hashtable来实现的，也就是说插入元素的时间复杂度为$O(1)$，所以这个方法的时间复杂度为$O(n)$
    受到这个的启发，实际上我们也可以通过构造类似的哈希结构来进行判断。