[448]Find All Numbers Disappeared in an Array

 

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

---

다음 출처를 참고하여 해결하였습니다.

ergate.tistory.com/entry/LeetCode-448-Find-All-Numbers-Disappeared-in-an-Array

 

중요한 성질 두 가지를 기억하면 됩니다.

 

N: 배열의 길이

1. 배열 내의 값이 [0,N-1] 또는 [1,N] 범위 내로 주어진다면 이를 인덱스로 활용할 가능성이 높습니다.

2. 중복유무와 관계없이 한 번이라도 등장한 값과 등장하지 않은 값의 차이는 인덱스상에 표시할 수 있습니다.

 

위 1, 2번 성질을 활용하여  한 번이라도 등장한 숫자는 number는 arr[number-1] 숫자를 음수로 바꿔줍니다.

 

중복 방문하지 않도록 하여 2번 등장한 숫자의 arr[number-1]이 양수가 되지 않게 합니다.

 

이렇게 바꿔버린 뒤에 아직 arr[] 원소값이 양수라면 이 인덱스는 등장하지 않은 숫자임을 알 수 있습니다.

---

public List<Integer> findDisappearedNumbers(int[] nums) {

    List<Integer> duplicatedNumbers = new ArrayList<>();

    for (int i = 0; i < nums.length; ++i)
    {
        int idx = Math.abs(nums[i]);

        if (nums[idx-1] > 0)
        {
            nums[idx-1] = -nums[idx-1];
        }
    }

    for (int i = 0; i < nums.length; ++i)
    {
        if (nums[i] > 0)
        {
        duplicatedNumbers.add(i + 1);
        }
    }

    return duplicatedNumbers;
}