540. Single Element in a Sorted Arrayhttps://leetcode.com/problems/single-element-in-a-sorted-array/

题目描述

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5

解题思路

【C++】

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

【Java】

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int l = 0, h = nums.length - 1;
        while (l < h) {
            int m = l + (h - l) / 2;
            if (m % 2 == 1) {m--;} //保证 l/h/m 都在偶数位，使得查找区间大小一直都是奇数
            if (nums[m] == nums[m+1]) {l = m + 2;}
            else {h = m;}
        }
        return nums[l];
    }
}