질문

• 질문 링크

증가하는 숫자 배열을 제공하십시오.

모든 값은 쌍으로 존재하며 하나의 값만 존재합니다.

문제는 하나만 있는 값을 찾는 것입니다.

해결책

Map 만 사용하는 것은 문제가 있지만 추가 조건으로 O(log n) time and O(1) space 요구의 복잡성

이 조건을 만족하기 위해서는 이진 탐색이 필요하다.

그러나 이 질문은 일반적인 이진 검색과 달리 조회할 값을 별도로 주지 않는다.

따라서 범위를 반으로 나눌 때 찾고 있는 값이 왼쪽에 있는지 오른쪽에 있는지 알 수 있습니까?

힌트는 “각 숫자는 2개여야 합니다”입니다.

확실히 연속으로 두 개가 있기 때문에 인덱스 위치를 찾아 숫자를 비교하면 값이 하나만 있는 곳을 찾을 수 있습니다.

대신 현재 인덱스가 홀수인지 짝수인지에 따라 비교 대상이 달라지므로 그 부분만 확인하면 된다.

자바 코드

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);
    }
}