442._Find_All_Duplicates_in_an_Array.md

442. Find All Duplicates in an Array

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/find-all-duplicates-in-an-array/description/

内容描述

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

解题方案

思路 1

直接用个字典存一下key和出现次数，然后loop一遍

• 时间复杂度O(n)
• 空间复杂度O(n)

class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res, lookup = [], {}
        for num in nums:
            lookup[num] = lookup.get(num, 0) + 1
        for key in lookup.keys():
            if lookup[key] == 2:
                res.append(key)
        return res

思路 2

把每个数字都放到正确的位置上去，a[0] = 1, a[1] = 2, a[2] = 3 ... etc. (1<=a[i]<=n).

参考ZhassanB

• 时间复杂度O(n)
• 空间复杂度O(1)

class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums or len(nums) == 0:
            return []
        res = []
        i, n = 0, len(nums)
        while i < n: # traverse the array  till the end
            if nums[i] == i+1: # if number stays at it's supposed position, just continue
                i += 1
                continue
            cur = nums[i]
            if cur == -1: # if the duplicate number in that position is already found continue
                i += 1
                continue
            if nums[cur-1] == cur: # if current num is equals to the number at supposed position,
                res.append(cur)    # then it is duplicate.
                nums[i] = -1       # mark this position, in order to denote that duplicate has found
                i += 1
                continue
            # if current number's supposed position is occupied by another number swap and consider that number
            nums[i], nums[cur-1] = nums[cur-1], nums[i]
        return res