[LeetCode] 442. Find All Duplicates in an Array [Python] 배열

leetcode.com/problems/find-all-duplicates-in-an-array/

Find All Duplicates in an Array - LeetCode

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?

 

이 문제는 주어진 배열에서 중복된 정수를 찾아내는 문제이다. 비슷한 문제를 풀었었는데, 그때는 중복된 숫자가 딱 한 개였었기 때문에 이진 탐색으로 추가 용량을 사용하지 않고 풀 수 있었다.

udou.tistory.com/entry/LeetCode-287-Find-the-Duplicate-Number-Python

[LeetCode] 287. Find the Duplicate Number [Python] 이진탐색

이번 문제는 중복되는 숫자들을 모두 찾는 문제이다. 역시나 extra space가 허용되지 않는다. 이 문제는, 사실 문제를 만든 사람이 어떠한 풀이 방법을 예상하고 만든 것 같다. 왜냐하면 문제 자체가 exactly twice라는 명시가 없다. 그 이유는, 3개 이상의 테스트 케이스는 애초에 유효한 인풋으로 받아들여지지 않기 때문이다. 따라서 중복되는 숫자는 숫자가 나온다면, 주어진 배열에서 더도 덜도 말고 정확이 2번 출현이 된 것이다. 이 문제를 해시 맵을 이용하여 풀면 runtime은 O(n)이 나오지만, space complexity 역시 O(n)이 나온다. 때문에 해시 맵을 따로 정의하지 않고, 주어진 배열 자체를 해시맵으로 생각하여 풀어보았다.

---

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

---

먼저 주어진 배열 안의 숫자 x는 1 <= x <= len(nums)의 조건을 만족한다. 이것을 이용하여 배열 안의 숫자 자체를 key로 생각해보자. 그 key를 인덱스로 보고, 해당 인덱스에 있는 값을 마이너스 값으로 바꾸어준다. 그렇게 for loop을 이용하여 iteration을 하다가 key에 해당하는 value가 음수일 경우 그 음수 값을 ans에 추가시켜준다. 아래는 [4,3,2,7,8,2,3,1] 예시로, 매 반복문이 실행될 때마다 배열 nums안의 값이 어떻게 변화되는지 볼 수 있다. 

---

4 [4, 3, 2, -7, 8, 2, 3, 1] []
3 [4, 3, -2, -7, 8, 2, 3, 1] []
-2 [4, -3, -2, -7, 8, 2, 3, 1] []
-7 [4, -3, -2, -7, 8, 2, -3, 1] []
8 [4, -3, -2, -7, 8, 2, -3, -1] []
2 [4, -3, -2, -7, 8, 2, -3, -1] [2]
-3 [4, -3, -2, -7, 8, 2, -3, -1] [2, 3]
-1 [-4, -3, -2, -7, 8, 2, -3, -1] [2, 3]

---

첫 번째 열은 nums[i] 값이며, 두 번째 열은 nums, 세 번째 열은 ans의 값이다. 해당 솔루션은 rumtime O(n)이 나오며 주어진 배열을 modify 하여 주어진 조건을 만족하는 extra space사용 없이 풀었다.