Leetcod540 有序数组中的单一元素
1.题目描述
2.解题思路
同样是二分搜索,利用当i为偶数时候,数组中单独元素左侧的所有i位置与i+1位置的数字相同,而单独元素右侧的所有i位置与i+1位置元素不同的特性,来进行二分搜索
3.算法思路
low = 0
high = nums.size()-1
while(low<high):
pow = (low + high) / 2 and pow % 2 == 1
if nums[pow] == nums[pow+1]:
low = pow + 2
else if nums[pow] != nums[pow+1]:
high = pow
return nums[low]
4.代码
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int low = 0;
int high = nums.size()-1;
while(low < high){
int pow = (low + high)/2;
if(pow%2 == 1){
pow--;
}
if(nums[pow] == nums[pow+1]){
low = pow + 2;
}else if(nums[pow] != nums[pow+1]){
high = pow;
}
}
return nums[low];
}
};