14. Find All Numbers Disappeared in an Array

문제

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

n개 정수가 들어있는 nums 배열이 있다.

1에서 n 범위의 숫자 중 nums 배열에 없는 요소를 배열 형태로 반환하라.

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

 

내가 생각한 방법

1) 사이즈가 n+1인 배열 hashArr를 생성하고 0으로 채움.

2) nums 배열을 i를 사용하여 0부터 끝까지 한 칸씩 탐색하면서

3) hashArr의 nums[i]번 값을 1씩 증가시킴 => hashArr에서 nums에 없는 인덱스 값만 0이 됨

4) hashArr를 탐색하며 값이 0인 경우, 인덱스를 returnArr에 저장

 

time complexity : O(n)

space complexity : hashArr 배열이 필요함 => 최고효율 x

vector<int> findDisappearedNumbers(vector<int>& nums) {
    int n = nums.size();
    // nums보다 1칸 더 큰 새 배열 생성하고 0으로 채움
    vector<int> hashArr(n + 1, 0);
    vector<int> returnArr;

    // nums 배열을 0부터 끝까지 한 칸씩 탐색
    // nums[i] 값을 hashArr 배열 인덱스로 사용해서 hashArr[nums[i]]에 1 더함
    // 최종적으로 hashArr에서 nums 배열에 없는 인덱스의 값만 0이 됨
    for (int i = 0; i < n; i++){
        hashArr[nums[i]]++;
    }

    // hashArr 배열 탐색해서 값이 0인 경우, 인덱스를 returnArr에 저장
    for (int i = 1; i < n + 1; i++){
        if (hashArr[i] == 0){
            returnArr.push_back(i);
        }
    }

    return returnArr;
}

 

다른 해결 방식(python3)

space complexity O(1)인 방법

https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/discuss/344583/Python%3A-O(1)-space-solution

 

1) nums 배열을 iterate : 각 요소가 가리키는 인덱스 - 1로 가서, 해당 인덱스 요소를 -로 표시.

(ex. nums는 [4, 3, 2, 7, 8, 2, 3, 1]. 5, 6이 빠져있음.

nums[0]은 4 => nums[3]의 요소 7을 -7로 변경

nums[1]은 3 => nums[2]의 요소 2를 -2로 변경 ...)

 

iterate 후 빠진 숫자 - 1의 인덱스는 음수 처리가 안 되어 있음

(ex. nums는 [-4, -3, -2, -7, 8, 2, -3, -1]이 됨. 4번, 5번 인덱스의 숫자만 양수)

 

2) 다시 iterate해서 양수인 숫자의 인덱스+1을 result에 담아 반환.

def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
    for i in range(len(nums)):
        current = abs(nums[i]) - 1
        if nums[current] > 0:
            nums[current] *= -1

    result = []

    for index, value in enumerate(nums):
        if value > 0:
            result.append(index + 1)

    return result