[LeetCode] 540. Single Element in a Sorted Array

김민우·2023년 2월 21일

알고리즘

목록 보기

146/189

- Problem

- 내 풀이 1 (bit masking)

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        answer = 0
        
        for num in nums:
            answer = xor(answer, num)

        return answer

~~친절하게도~~ 하나의 정수를 제외한 모든 정수는 두 개씩 나온다. 나와 나 자신을 xor한 연산은 0이 나오며, 따라서, 주어진 배열 nums 를 모두 xor 연산하게 되면 하나만 존재하는 숫자를 찾을 수 있게 된다.

reduce 함수를 이용하면 다음과 같이 한 줄로 작성도 가능하다.

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        return reduce(xor, nums)

- 결과

시간 복잡도: O(N)
공간 복잡도: O(1)

해당 문제는 시간 복잡도 O(N)으로도 충분히 풀 수 있는 문제다.
하지만, 문제에서 제시하는 시간 복잡도는 O(logn)이다. 따라서, O(logn)을 만족하는 접근법을 찾아야 한다.

- 내 풀이 2 (이분 탐색)

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 2

        while left <= right:
            mid = (left + right) // 2

            if mid % 2: # odd
                if nums[mid] == nums[mid-1]:
                    left = mid + 1
                
                else:
                    right = mid - 1

            else: # even
                if nums[mid] == nums[mid+1]:
                    left = mid + 1
                
                else:
                    right = mid - 1

        return nums[left]

시간 복잡도 log(n)을 만족하기 위해 이분탐색을 이용한다.
주어지는 nums는 오름차순으로 정렬이 되어 있으며, 어느 정도 규칙성이 보이는 배열이다.

어떠한 조건에 따라 left, right 값을 이동시킬지가 관건이다. 두 번째 예제를 잘 살펴본다면 규칙이 보인다.

nums = [3,3,7,7,10,11,11] 배열에서, single element인 10이 나타나기 전인 [3,3,7,7]을 봐보자.

mid 값이 짝수일 경우,
- mid값이 0 혹은 2일 경우, nums[0] = nums[1], nums[2] = nums[3]인 규칙을 보인다.
mid 값이 홀수일 경우,
- mid값이 1 혹은 3일 경우, nums[1] = nums[0], nums[3] = nums[2]인 규칙을 보인다.