[LeetCode] Java 448. Find All Numbers Disappeared in an Array

448번 문제 : 배열에서 사라진 모든 숫자 찾기 (풀이 소스) 

 

 

1차 접근은 정렬을 먼저하고, 중복된 값을 제거하여 list로 담은 다음, 1부터 증가한 값부터 비교하여

값이 다르면 그 값을 담으려고 했으나 구현상 문제가 있었다.

 

고민끝에, 방법을 찾는 도 중 Arrays API에 이분탐색 함수에서 Arrays.binarySearch() API가 제공 되는걸 알게 되었다.

 

아이디어는 '정렬시켜놓고 자기 자리 인덱스와 값을 비교해서 다른 숫자들 모두 후보군으로 둔다.

후보군에서 배열에 값이 없는 숫자가 진짜 없는 숫자' 입니다.

 

따라서 해당 알고리즘을 위해 정답 리스트를 선언하고 배열을 정렬하고 배열을 순회하며 후보군을 찾습니다. 후보군을 찾은 뒤에는 빠른 검색을 위해 binarySearch 메소드를 사용합니다. 

 

정렬된 배열에 한해 사용할 수 있으며, 해당 값이 있으면 해당 인덱스를 return 해주고 찾는 값이 없으면 -1를 return 합니다.

 

public List<Integer> findDisappearedNumbers(int[] nums) {
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if(nums[i] != i+1) {
                if(Arrays.binarySearch(nums, i+1) < 0) {
                    list.add(i+1);
                }
            }
        }

        return list;
}

 

 

참조사이트 : code0xff.tistory.com/68

참조사이트 : all-dev-kang.tistory.com/entry/LeetCode-%EC%9E%90%EB%B0%94-448-Find-All-Numbers-Disappeared-in-an-Array