[Algorithm] LeetCode 448. Find All Numbers Disappeared in an Array using ArrayList

• 문제해석
  • 1부터 n까지의 길이의 배열이 있고 배열에 있는 각각의 요소는 1과 n사이에 있는 수이다.
  • 따로 변수나 배열을 사용하지 않고 O(n)만에 문제를 풀어야 한다.
  • 배열을 순회하면서 하나씩 체크하면서 동시에 없는 수를 가려내야 한다.
• 헷갈린 부분
  
  • 따로 메모리를 쓰지 않는다는 것이 어떤 의미인가
    • 변수나 배열을 선언하지 않고 있는 배열내에서 해결하는 것을 의미한다.
  • int index = nums[i] - 1 하고 그 index를 다시 nums[index]로 하는데 이렇게 하는 이유가 무엇인지 한참 고민했다. 
  • 돌이켜보면 아무래도 문제를 확실하게 이해했다면 금방 풀릴 고민일수도 있을 것 같다. 
    • nums 배열의 요소 모두 1보다 크고 n보다 작으니 missing number가 있다면 중복되는 숫자가 분명히 있을 것이다. 
    • nums[i] 값으로 nums 인덱스를 판별한다
      • [4, 3, 2, 7, 8, 2, 3, 1]의 배열로 예를들면 
      • nums[4]-1의 값으로 nums의 인덱스에 접근해서 인덱스에 해당하는 값을 음수로 바꿔서 값을 체크한다.
      • 음수로 한번 바뀐값은 다시 돌리지 않는다. 
        • 따라서 음수로 한번 바뀐값은 다시 체크하지 않는다. 
      • 끝나고 양수인 값만 추려서 그 인덱스를 List에 넣는다.
        • 근데 사실 이부분도 약간 이해가 안간다. 더 찾아봐야겠다.

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        for(int i = 0; i < nums.length; i++){
            int index = Math.abs(nums[i])- 1;

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

참고

https://medium.com/@Zack123456/448-find-all-numbers-disappeared-in-an-array-3e3f764b3989