[leetcode540]有序数组中的单一元素

发布于 2022-02-14  170 次阅读


https://leetcode-cn.com/problems/single-element-in-a-sorted-array/

思路:满足分段二分性 将两个看成一组 前半部分符合两个相同 后半部分不符合两个相同 因此二分logn

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        nums.push_back(nums.back()+1);//后面补一个数 保证成偶数 
        int l=-1,r=nums.size()/2;//成对二分
        while(l+1!=r){
            int mid=l+r>>1;
            if(nums[mid*2]==nums[mid*2+1]){
                l=mid;
            }
            else{
                r=mid;
            }
        }
        return nums[r*2];
    }
};

 


愿风指引你的道路,愿你的刀刃永远锋利。