540. 有序元素中的单一元素

题目描述

链接: https://leetcode-cn.com/problems/single-element-in-a-sorted-array/
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例 1:

输入: [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:

输入: [3,3,7,7,10,11,11]
输出: 10
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

代码(二分法):

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            // 防止溢出
            int mid = low + (high - low) / 2;
            // 如果左边是一样的数, mid--, 如果右面是一样的数, 不动(保持mid在同一个数的最左侧)
            if (mid-1 >= 0 && nums[mid-1] == nums[mid]) {
                mid--;
            } else if (mid+1 < nums.length && nums[mid+1] == nums[mid]) {
            } else {
                return nums[mid];
            }
            // 左侧有奇数个, 说明左侧一定有单身数字
            // 左侧有偶数个, 说明左侧没有(单身数字只有一个), 往后跳两个
            if ((mid - low) % 2 == 1) {
                high = mid - 1;
            } else  {
                low = mid + 2;
            }
        }
        return -1;
    }
}

思路:

1) 直接所有异或,最后剩下的就是单身数字, O(n)时间复杂度, O(1)空间复杂度
2) 用二分法(因为是有序数组)