來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array

題目描述

給你一個僅由整數(shù)組成的有序數(shù)組，其中每個元素都會出現(xiàn)兩次，唯有一個數(shù)只會出現(xiàn)一次。

請你找出并返回只出現(xiàn)一次的那個數(shù)。

你設(shè)計的解決方案必須滿足 O(log n) 時間復(fù)雜度和 O(1) 空間復(fù)雜度。

?

示例 1:

輸入: nums = [1,1,2,3,3,4,4,8,8]
輸出: 2

示例 2:

輸入: nums = [3,3,7,7,10,11,11]
輸出: 10
?

提示:

1 <= nums.length <= 10⁵
0 <= nums[i]?<= 10⁵

?

解題思路

本題難點在于限制了時間復(fù)雜度和空間復(fù)雜度，根據(jù)時間復(fù)雜度來看，很明顯在誘導(dǎo)解題者使用二分法解題。

首先尋找規(guī)律，單一元素a的左邊必然有偶數(shù)個元素，所以a的坐標(biāo)必然是偶數(shù)，并且，a左邊偶數(shù)坐標(biāo)left的值均與left+1的值相同，右邊偶數(shù)坐標(biāo)right的值與right-1的值相同，所以，只需要找到這個分界點就是單一元素。

使用二分法，左邊界left設(shè)置為0，右邊界right設(shè)置為最大的偶數(shù)坐標(biāo)，求出中間的偶數(shù)坐標(biāo)mid（如果是奇數(shù)需要-1變成偶數(shù)坐標(biāo)）判斷是否nums[mid] == nums[mid + 1],如果相同，則a在mid的右邊，并且mid不可能為單一元素，將left設(shè)置為mid + 2；否則，a可能在mid左邊，也可能就是mid，所以將right設(shè)置為mid。

代碼展示

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int iLeft = 0, iRight = nums.size() - 1, iMid = 0;
        if(iRight % 2)
            iRight--;
        while(iLeft < iRight)
        {
            iMid = (iLeft + iRight) / 2;
            if(iMid % 2)
                iMid --;
            if(nums[iMid] == nums[iMid + 1])
                iLeft = iMid + 2;
            else
                iRight = iMid;
        }
        return nums[iLeft];
    }
};

運行結(jié)果

?