來(lái)源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/single-element-in-a-sorted-array
題目描述
給你一個(gè)僅由整數(shù)組成的有序數(shù)組,其中每個(gè)元素都會(huì)出現(xiàn)兩次,唯有一個(gè)數(shù)只會(huì)出現(xiàn)一次。
請(qǐng)你找出并返回只出現(xiàn)一次的那個(gè)數(shù)。
你設(shè)計(jì)的解決方案必須滿足 O(log n) 時(shí)間復(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 <= 105
0 <= nums[i]?<= 105
?
解題思路
本題難點(diǎn)在于限制了時(shí)間復(fù)雜度和空間復(fù)雜度,根據(jù)時(shí)間復(fù)雜度來(lái)看,很明顯在誘導(dǎo)解題者使用二分法解題。
首先尋找規(guī)律,單一元素a的左邊必然有偶數(shù)個(gè)元素,所以a的坐標(biāo)必然是偶數(shù),并且,a左邊偶數(shù)坐標(biāo)left的值均與left+1的值相同,右邊偶數(shù)坐標(biāo)right的值與right-1的值相同,所以,只需要找到這個(gè)分界點(diǎn)就是單一元素。
使用二分法,左邊界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]; } };
運(yùn)行結(jié)果
?
本文摘自 :https://www.cnblogs.com/