[Array] Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

 

 

오름차순 정렬을 하면 연속된 값을 가져하는 배열에 빠진 원소가 있다

이 원소를 찾아라..! 하는 문제

역시나 시간이 좀 걸렸지만..

 

1) 배열의 인덱스 자체가 값과 같아야 함을 이용하자

-> 즉, 배열이 [1,2,3,5]라고 들어오는데 이를 그대로 인덱스로 이용한다면 4번 인덱스가 다른 원소들과 다를것이다

2) 해당하는 인덱스들만 표시를 해놓자. 여기선 새로 배열을 만들지 말라니까 음수로 바꾸자