首页 > itarticle > leetcode442: find all duplicates in an array 2. Analysis 3. Solution(s)

leetcode442: find all duplicates in an array 2. Analysis 3. Solution(s)

admin 11月 12, 2020 0

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]

2. Analysis

3. Solution(s)

class (object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = list()
        for i in xrange(len(nums)):
            if nums[abs(nums[i])-1] > 0:
                nums[abs(nums[i])-1] *= -1
            else:
                res.append(abs(nums[i])) 
        return res