動機

  1. LC不講武德，不小心按到組合鍵就被submit了
  2. bsearch的重點是要丟棄的範圍

Problem

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.

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105

sol

其實就是一直讓長度保持成奇數就好，所以要丟棄長度為偶數的部分

class Solution:
    def bsearch(self, i, j):
        if j - i <= 1:
            return self.nums[i]
        mid = ((j-i) // 2) + i
        #print(f'{i} {j}')
        #print(f'{self.nums[i:mid]} {self.nums[mid]} {self.nums[mid+1:j]}')
        if self.nums[mid] != self.nums[mid-1] and self.nums[mid] != self.nums[mid+1]:
            return self.nums[mid]
        elif self.nums[mid] != self.nums[mid-1]:
            # i .. mid mid+1 .. j
            if (mid - i) % 2 != 0:
                #print(f'B {i} {mid}')
                return self.bsearch(i, mid)
            else:
                #print(f'A {mid+2} {j}')
                return self.bsearch(mid+2, j)
        else:
            # i .. mid-1 mid .. j
            if (mid-1 - i) % 2 != 0:
                #print(f'C {i} {mid-2}')
                return self.bsearch(i, mid-1)
            else:
                #print(f'D {mid+1} {j}')
                return self.bsearch(mid+1, j)
    def singleNonDuplicate(self, nums: List[int]) -> int:
        self.nums = nums
        return self.bsearch(0, len(nums))