描述

给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

示例

示例 1:

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

示例 2:

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

提示

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105


解题思路

  • 我们的数组个数始终是奇数，因为有一个元素出现一次，其余元素出现两次。
  • 用二分查找，首先判断 mid 元素是否是唯一元素，是的话直接返回。否则，去掉与 mid 相同的元素，此时数组分为两个新的部分，答案在的那一边元素个数始终为奇数，根据这个性质继续二分。

代码

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right)/2;
            if (mid == 0 || mid == n - 1) return nums[mid];
            if (nums[mid - 1] == nums[mid]) {
                if ((mid - 2) % 2 == 0) { //数字在左边
                    right = mid - 2;
                } else {
                    left = mid + 1;
                }
            } else if (nums[mid + 1] == nums[mid]) {
                if ((mid - 1) % 2 == 0) { //数字在左边
                    right = mid - 1;
                } else {
                    left = mid + 2;
                }
            } else {
                return nums[mid];
            }
        }
        return -1; 
    }
}

复杂度分析

  • 时间复杂度：O(logn)。在每次循环迭代中，我们将搜索空间减少了一半。
  • 空间复杂度：O(1)，仅使用了常数空间。