leetcode 442 Find All Duplicates in an Array
z
 2019-06-08 11:39:29  

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:

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

Output:
[2,3]
  • 在一个长度为n的数组中，每一个数的范围为1~n。其中存在一些数出现的次数为两次，要求找出这些数。
  • 如果空间要求不为O(1)的话，可以通过哈希表的方式在做。但是现在空间要求为O(1)，我们不能额外建立哈希表。考虑到nums数组的长度为n，他本身就适合做哈希表。
  • 我们从0~n-1遍历nums的每一个元素，假设当前正在遍历第i个元素，nums[i] = x，那么为了记录下x出现过一次，我们将nums[x-1]变为乘以-1，表示x出现过一次。
  • 因此，我们每一次遍历到一个新的元素nums[j]时，我们判断nums[nums[j]-1]的位置是否为负数，如果是负数的话，就表示nums[j]-1曾经出现过，那么将其加入到ans集合中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ans = []
        for i in range(len(nums)):
            idx = abs(nums[i])-1
            if nums[idx] < 0:
                ans.append(idx+1)
            else:
                nums[idx] *= -1
        return ans