LeetCode刷题实战540：有序数组中的单一元素-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 有序数组中的单一元素，我们先来看题面：

https://leetcode-cn.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.

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: nums = [3,3,7,7,10,11,11]
输出: 10

解题

看到"有序数组"， “ O(log n)时间复杂度和 O(1)空间复杂度”,就应该想到“二分搜索法”。代码如下：

class Solution {
    public int singleNonDuplicate(int[] nums) {
   int left = 0;
        int right = nums.length - 1;
        while (left < right){
            int mid = left + (right - left) / 2;
            if (nums[mid] == nums[mid + 1]){ // 和u右边相等
                int c = mid - left; //mid左边个数
                if (c%2 == 0){ // 偶数个
                    left = mid + 2;
                }else{
                    right = mid - 1;
                }
            }else if (nums[mid] == nums[mid - 1]){
                int c = right - mid; // mid右边个数
                if (c%2 == 0){ // 偶数个，说明在左边
                    right = mid - 2;
                }else{ // 奇数个，说明在右边
                    left = mid + 1;
                }
            }else{ // 1,1,2,3,3, 不等于右边，也不等于右边，直接返回
                return nums[mid];
            }
        }

        return nums[left];
    }
}