[Leetcode] 442. Find All Duplicates in an Array

문제:

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.

 

내가 짠 코드 

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        count_dict = {}
        output_list = []
        for num in nums:
            if num not in count_dict:
                count_dict[num] = 1 
            else:
                output_list.append(num)
        return output_list

나는 dictionary를 한 개 만들고, iteration을 돌렸다. dictionary에 속해있는 num값이 나오는 순간 output_list에 추가하였다. 이 방법은 count가 따로 필요 없어, 효율성이 좋다고 생각했다. 

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        ans =[]
        n=len(nums)
        for x in nums:
            x = abs(x)
            if nums[x-1]<0:
                ans.append(x)
            nums[x-1] *= -1
        return ans

이 코드는 leetcode solution 중 하나다. 접근방법이 상당히 독특했다. 자기값 - 1에 -1을 곱함으로 인해 처음 값을 발견했을 때  -값을 갖게 된다. 다음 루프 때 똑같은 값이 발견되면, ans 리스트에 추가해 준다. 상당히 괜찮은 방법이다.