442.Find All Duplicates in an Array

Tags: [swap]

Link: https://leetcode.com/problems/find-all-duplicates-in-an-array/?tab=Description

Given an array of integers, 1 ≤ a[i] ≤n(n= size of array), some elements appeartwiceand others appearonce.

Find all the elements that appeartwicein 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]

Solution: swap

class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums:
            return []

        index = 0
        while index < len(nums):
            curr = nums[index]
            if index + 1 == curr or curr == nums[curr - 1]:
                index += 1
                continue

            nums[index], nums[curr - 1] = nums[curr - 1], nums[index]

        rest = []
        for i in xrange(len(nums)):
            if i + 1 != nums[i]:
                rest.append(nums[i])

        return rest

Note:

• Time complexity = O(n), n is the number of the given numbers.