動機

又一個有趣的手法

Problem

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

 

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]Output: [2,3]

Example 2:

Input: nums = [1,1,2]Output: [1]

Example 3:

Input: nums = [1]Output: []

 

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n
  • Each element in nums appears once or twice.

Sol

因為資料與index只差1，所以可以一直把資料換到對的位置，最後走一遍看哪裡出事

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            while i != nums[i]-1 and nums[i] != nums[nums[i]-1]:
                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
                #print(nums)
        return [v for (_,v) in filter(lambda iv: iv[0]+1 != iv[1], enumerate(nums))]