Problem
숫자만 존재하는 오름차순 배열이 주어집니다.
모든 값들은 2개씩 존재하고 단 하나의 값만 1개 존재합니다.
1개만 존재하는 값을 찾는 문제입니다.
Solution
그냥 Map 을 사용해도 되는 문제지만 추가 조건으로 O(log n) time and O(1) space
의 복잡도를 요구합니다.
이 조건을 만족하기 위해선 이분탐색이 필요합니다.
하지만 이 문제는 일반적인 이분탐색과 다르게 찾아야 하는 값이 따로 주어지지 않습니다.
그럼 범위를 절반으로 나누었을 때 왼쪽과 오른쪽 중 찾으려는 값이 있는 곳을 알 수 있을까요?
힌트는 "모든 숫자는 반드시 두개씩 존재한다" 입니다.
반드시 두개씩 연달아 존재하기 때문에 인덱스 위치를 파악해서 숫자를 비교하면 단 하나만 있는 값의 위치를 알 수 있습니다.
대신 현재 index 가 홀수인지 짝수인지에 따라 비교해야 하는 대상이 바뀌기 때문에 그 부분만 체크해주면 됩니다.
Java Code
class Solution {
public int singleNonDuplicate(int[] nums) {
int left = 0;
int right = nums.length - 1;
int mid = 0;
while (left < right) {
mid = (left + right) / 2;
if (mid % 2 == 0 && nums[mid] == nums[mid + 1]) {
// mid 위치가 짝수면 오른쪽 값이랑 비교하고 같으면 single 은 오른쪽에 있음
left = mid + 2;
} else if (mid % 2 == 1 && nums[mid] == nums[mid - 1]) {
// mid 위치가 홀수면 왼쪽 값이랑 확인하고 같으면 single 은 오른쪽에 있음
left = mid + 1;
} else {
// 위에 전부 해당 안되면 single 은 왼쪽에 있음
right = mid;
}
}
return nums[left];
}
}
'알고리즘 문제 > LeetCode' 카테고리의 다른 글
[LeetCode Medium] Count Number of Teams (Java) (1) | 2023.03.15 |
---|---|
[LeetCode Medium] Triangle (Java) (3) | 2023.03.09 |
[LeetCode Medium] Robot Bounded In Circle (Java) (0) | 2021.04.08 |
[LeetCode Easy] Partition Array Into Three Parts With Equal Sum (Java) (2) | 2021.04.08 |
[LeetCode Easy] Add Binary (Java) (0) | 2021.04.08 |