문제는 '배열에 없는 숫자 찾기, 없는 숫자란 배열 크기의 정수중에 없는 숫자를 뜻함'
첫번째.
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
Arrays.sort(nums);
List<Integer> result = new ArrayList<>();
for(int i =0; i< nums.length; i++){
if(nums[i] != i+1) {
if(Arrays.binarySearch(nums, i+1)<0){
result.add(i+1);
};
}
}
return result;
}
}
아이디어는 '정렬시켜놓고 자기 자리 인덱스와 값을 비교해서 다른 숫자들 모두 후보군으로 둔다. 후보군에서 배열에 값이 없는 숫자가 진짜 없는 숫자' 입니다.
따라서 해당 알고리즘을 위해 정답 리스트를 선언하고 배열을 정렬하고 배열을 순회하며 후보군을 찾습니다. 후보군을 찾은 뒤에는 빠른 검색을 위해 binarySearch 메소드를 사용합니다.
binarySearch 에 대해 잠깐 살펴보겠습니다.
정렬된 배열에 한해 사용할 수 있으며, 해당 값이 있으면 해당 인덱스를 return 해주고 찾는 값이 없으면 -1를 return
따라서 0보다 작을때 없는 값임으로 정답 리스트에 넣어주면 끝입니다.
'코딩테스트 > Leet Code' 카테고리의 다른 글
[LeetCode] 자바, 20. Valid Parentheses (0) | 2020.08.10 |
---|---|
[LeetCode] 자바 53. Maximum Subarray (0) | 2020.08.10 |
[LeetCode] 자바 169. Majority Element (0) | 2020.08.09 |
[LeetCode] 자바, 283. Move Zeroes (0) | 2020.08.09 |
[LeetCode] 자바 136. Single Number (0) | 2020.08.08 |
댓글