[数据结构与算法]540. Single Element in a Sorted Array

依次遍历数字即可， 不过不是i++ ，而是i=i+1, 最后返回的为什么是nums[nums.size()-1]，因为如果for循环没有找到，此时for的设置只会遍历i*n个数字，说明还有最后一个数字没有遍历，那么就是最后一个数字不是重复的。

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        //找到非重复的数字
        //非重复数字特点 和左边一个和右边一个均不相等
        for(int i=0; i<nums.size()-1; i+=2){
            if(nums[i]!=nums[i+1]) return nums[i];
        }
        return nums[nums.size()-1];
    }
};

或者采用二分的方法，因为如果只出现一次的数字没有出现的话 下标就会呈现01 23 45 67，前偶后奇数， 这时候需要查找后半部分。但是如果出现一次的数字，那么变成前奇数后偶数，那么需要查找前半部分。

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

2022深度学习开发者峰会

5月20日13:00让我们相聚云端，共襄盛会！