540. Single Element in a Sorted

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1:
Input: [1,1,2,3,3,4,4,8,8]
Output: 2
Example 2:
Input: [3,3,7,7,10,11,11]
Output: 10

Note: Your solution should run in O(log n) time and O(1) space.

思路:很简单,既然按递增顺序排列,比乱序好做的多,因为重复的数字总是相邻,用增量法即可解.由于只有一个数出现单次,其余均出现两次,观察易知单次的数必出现在偶数下标(数组从0开始),因此用一个计数器求和,遍历数组,下标为奇则取元素负值,累加;下标为偶则取元素正值,累加.
最终求和结果就是只出现一次的数.

int singleNonDuplicate(vector<int>& nums) {
        int sum = 0;  //求和
        for (int i = 0; i < nums.size(); i++) {
            if (i%2 == 0) sum += nums[i];  //下标为偶,加之(取正值)
            else sum -= nums[i];  //下标为奇,减之(取负值)
        }
        return sum;
    }