Leetcode題解 Python & C#：五月挑戰DAY12 Single Element in a Sorted Array

給一個經排序後的數列，找出其中只出現一次的元素。(其他重複二次)

被限制在 時間複雜度 O(log n) 和 空間複雜度 O(1)，解決。

說到 O(log n) time ，經典的方式是二分法。

由於其他都出現二次，可想 pos % 2 == 0 的位置會等於其右方的，除非有出現單次的元素在左方。

用二分搜尋法，計算的 m 在比較的時候要用 % 2 修正位置，去讓奇數位比其右方的位罝。

這裡的 r 跟往不同減了 1 ，是因應「超界」做處理，如果出現單次的在最右方，那麼一般的二分搜尋法，會在比較時比 nums[n] 。如果左方都出現兩次，那最後 r 值不變，指向最後一個為單一的元素。

Python

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:        
        l, r = 0, len(nums)-1
        while l < r:
            m = (r-l)//2 + l
            if nums[m-m%2] == nums[m+1-m%2]:
                l = m+1
            else:
                r = m
        return nums[r]

C#

public class Solution {
    public int SingleNonDuplicate(int[] nums) {
        int l = 0; int r = nums.Length-1;
        while(l < r)
        {
            int m = (r-l)/2 + l;
            if(nums[m - m%2] == nums[m - m%2 + 1])
            {
                l = m + 1;
            }
            else
            {
                r = m;
            }
        }
        return nums[r];
    }
}