?LeetCode刷題實戰(zhàn)540：有序數(shù)組中的單一元素
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.
示例? ? ? ? ? ? ? ? ? ? ? ? ?
示例 1:
輸入: nums = [1,1,2,3,3,4,4,8,8]
輸出: 2
示例 2:
輸入: nums = [3,3,7,7,10,11,11]
輸出: 10
解題
class?Solution?{
????public?int?singleNonDuplicate(int[] nums)?{
???int?left = 0;
????????int?right = nums.length - 1;
????????while?(left < right){
????????????int?mid = left + (right - left) / 2;
????????????if?(nums[mid] == nums[mid + 1]){ // 和u右邊相等
????????????????int?c = mid - left; //mid左邊個數(shù)
????????????????if?(c%2?== 0){ // 偶數(shù)個
????????????????????left = mid + 2;
????????????????}else{
????????????????????right = mid - 1;
????????????????}
????????????}else?if?(nums[mid] == nums[mid - 1]){
????????????????int?c = right - mid; // mid右邊個數(shù)
????????????????if?(c%2?== 0){ // 偶數(shù)個，說明在左邊
????????????????????right = mid - 2;
????????????????}else{ // 奇數(shù)個，說明在右邊
????????????????????left = mid + 1;
????????????????}
????????????}else{ // 1,1,2,3,3, 不等于右邊，也不等于右邊，直接返回
????????????????return?nums[mid];
????????????}
????????}
????????return?nums[left];
????}
}