442. Find All Duplicates in an Array

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

一列数，1 ≤ a[i] ≤ n (n = size of array)，有的出现一次有的出现两次，输出出现两次的数。

Example:

Input:

[4,3,2,7,8,2,3,1]

Output:

[2,3]

耿直的你大概会写出如下代码

class Solution(object):

    def findDuplicates(self, nums):

        myset=set()

        for x in nums:

            if nums.count(x)==2:

                myset.add(x)

        return list(myset)

这就是engineering和science的区别，在工程中可能要统计2，也有可能以后需求要变会统计100，这时候这个代码改动就少

但是这可是LeetCode，在遍历中用count（）妥妥会TLE，题目也说了Could you do it without extra space and in O(n) runtime?

这时候你就需要用到各种奇技淫巧了

注意到：

1、数组内元素只会出现一次或两次，没有其他的情况。

2、所有元素都是正整数，且大于等于1

然后你突开脑洞，把数组遍历，将nums[x-1]的数翻面变负，如果在遍历中判断的时候发现这个数已经是负的了，说明出现了两次

class Solution(object):

    def findDuplicates(self, nums):

        res = []

        for x in nums:

            if nums[abs(x) - 1] < 0:

                res.append(abs(x))

            else:

                nums[abs(x) - 1] *= -1

        return res

什么？觉得有点看不懂？来个简单易懂的，也能过

class Solution(object):

    def findDuplicates(self, nums):

        res = []

        for x in nums:

            nums[abs(x) - 1] *= -1

        for x in nums:

            if nums[abs(x) - 1] > 0:

                res.append(abs(x))

        return list(set(res))

巴特西

442. Find All Duplicates in an Array

最新文章

热门文章