LeetCode: Single Element in a Sorted Arrayを解く

問題

May Leetcoding Challange Complementの12日目です。

leetcode.com

以下のノートの書きっぷりから二分探索のにほひがプンプンします。 実際、二分探索の問題でした。

Note: Your solution should run in O(log n) time and O(1) space.

解き方

場合分けのパターンが多い and 偶数奇数で判定する二分探索です。

以下に雑にパターンを描きました。（クソ雑）

回答

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

LeetCodeの解説だと、「Single Elementより前のペアの1番目はかならず偶数、Single Elementより後のペアの1番目はかならず奇数」という性質に注目して O(log n/2) の計算量で計算する回答もありました。

def singleNonDuplicate(self, nums: List[int]) -> int:
    lo = 0
    hi = len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if mid % 2 == 1:
            mid -= 1
        if nums[mid] == nums[mid + 1]:
            lo = mid + 2
        else:
            hi = mid
    return nums[lo]

計算量

時間計算量: O(logN)
空間計算量: O(1)