leetcode_442

发表于   |   分类于

Find All Duplicates in an Array

题目戳这

题意

给定一个数组，数组中有些数字只出现一次，有些数字出现两次，返回那些出现过两次的数字，不用额外的空间，以及利用线性的时间复杂度。

解法

注意题目中有说数组中的数范围为1<=a[i]<=n，所以我们可以利用这一点来对数字进行标记。题目说不用额外的空间，那我们又必须得标记，唯一的方法就是在原数组上进行标记。每出现一个数字x，我们就先取y=abs(x)，标记的方法就是使得a[y-1]取反(因为数组下标是0-n-1的，所以对y-1取反)，这样既不会破坏原来的数值，也达到了标记的效果，如果y再次出现，那么a[y-1]就是负数，此时说明x出现了两次。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        
        res = []
        for x in nums:
            y = abs(x)
            if nums[y-1] < 0:
                res.append(y)
            else:
                nums[y-1] *= -1
                
        return res