Leetcode 540. Single Element in a Sorted Array with Python

문제

You are given a sorted array consisting of only integers 
where every element appears exactly twice, 
except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

정수로만 이루어진 오름차순으로 정렬된 배열이 주어진다.
모든 원소는 하나를 제외하면 모두 2번 반복한다.
반복하지 않는 원소 하나를 찾아 리턴하시오.

시간복잡도 O(log n), 공간복잡도 O(1) 안에 해결하시오.

예시

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Input: nums = [3,3,7,7,10,11,11]
Output: 10

제한

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5

풀이법

전체적으로는 이진탐색방식을 사용한다.

이진 탐색으로 mid를 찾았을때는 아래와 같은 경우로 나뉠수 있습니다.

1. 두개 있는 값의 경우

반복되는 값은 앞에 값 한개짜리가 없을 경우 0, 1 // 2, 3 // 4, 5 // ~~ 의 Index를 가지게 됩니다.

즉 짝수 - 홀수 쌍의 Index를 가집니다.

허나 앞에 값이 한개짜리가 들어오면 이는 어그러져

홀수 - 짝수 쌍의 Index를 가지게 됩니다.

이를 확인해 Binary search의 다음 방향을 정하게 됩니다.

2. 한개 있는 값의 경우

자신의 양 옆을 확인해 자신과 다를 경우 리턴하면 됩니다.

코드

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        if len(nums) == 1: return nums[0]
        
        left = 0
        right = len(nums)-1
        while True:
            mid = (left + right) // 2
            if mid == 0:
                if nums[0] == nums[1]:
                    left = mid + 2
                else:
                    return nums[0]
            elif mid == len(nums)-1:
                if len(nums)-1 == len(nums)-2:
                    right = mid - 2
                else:
                    return nums[len(nums)-1]
            elif mid % 2 == 1:
                if nums[mid-1] == nums[mid]:
                    left = mid + 1
                elif nums[mid] == nums[mid+1]:
                    right = mid - 1
                else:
                    return nums[mid]
            elif mid % 2 == 0:
                if nums[mid+1] == nums[mid]:
                    left = mid + 2
                elif nums[mid-1] == nums[mid]:
                    right = mid - 2
                else:
                    return nums[mid]