leetcode442--Find All Numbers Duplicated in an Array

leetcode442--Find All Numbers Duplicated in an Array

题目

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]


不难是不太难,关键是要优化


class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        
        flag = [0]*len(nums)
        
        for x in nums:
            flag[x-1] += 1
        
        ret = []
        for i, x in enumerate(flag):
            if x==2:
                ret.append(i+1)
        return ret

在网上看到大神做这一类的题目是这样子做的

class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = []
        for x in nums:
            if nums[abs(x)-1] < 0:
                res.append(abs(x))
            else:
                nums[abs(x)-1] *= -1
        return res



即遍历每一个数字x,如果nums[abs(x)-1] <0 的话,说明这个数字就是重复的于是ret.append(abs(x)), 否则的话就nums[abs(x)-1] *= -1,

道理也很明白,就是出现过的话就在那个位置上等于其相反数,如果遍历的时候,发现这个数字是负的,说明之前已经出现过了,如果只出现一次的话就不会出现这种情况.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦