LeetCode_二分搜索_中等_540.有序数组中的单一元素

1.题目

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

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

你设计的解决方案必须满足 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

提示：
1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/single-element-in-a-sorted-array

2.思路

（1）二分搜索
思路参考该 LeedCode 用户题解。

题目要求算法的时间复杂度为 O(logn)，所以首先想到二分搜索，但是关键在于如何对数组 nums 进行二分。

① 由题目可知，有序数组中每个元素都会出现两次，唯有一个数只会出现一次，以数组 [1, 1, 2, 3, 3, 4, 4, 8, 8] 为例，元素 2 只出现了一次；
② 如果将元素 2 去掉，那么数组中的所有元素均出现了2 次，并且可以组成 4 个相等数对：[1, 1]、[3, 3]、[4, 4]、[8, 8]，但是 2 的出现，破坏了原来的相等数对（并且数组长度也由偶数变成了奇数）：[1, 1]、[2 3]、[3, 4]、[4, 8]、[8, ]；
③ 此时我们可以发现：元素 2 之前的相等数对仍然存在，而之后的相等数对被破坏，所以我们将这一点作为二分的依据！

3.代码实现（Java）

//思路1————二分搜索
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int length = nums.length;
        int left = 0;
        int right = length / 2;
        while (left < right) {
            int mid = (left + right) / 2;
            int index = mid * 2;
            if (nums[index] != nums[index + 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
16
17
18
19
20