leetcode 540. Single Element in a Sorted Array_java给定一个从小到大有序整数序列(可以是正整数,也可以是负整数)nums数组,

1.题目

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.
一个有序的整型数组，除一个元素只出现一次外，其余元素均出现两次。找出这个只出现一次的元素。
要求：时间复杂度O(logn),空间复杂度O(1)
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

2.分析

时间复杂度要求O(logn)，可以选用二分查找。

观察数组可以发现这样一个规律：对于数组S
在只出现一次的元素A出现之前，所有S[2*i]=S[2*i+1]
我们可以依据这一规律来判断A在当前位置的左边还是右边。

3.代码

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

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15