二分查找题目：有序数组中的单一元素

题目

标题和出处

标题：有序数组中的单一元素

出处：540. 有序数组中的单一元素

难度

4 级

题目描述

要求

给定一个仅由整数组成的升序数组，其中每个元素都出现两次，除了一个元素只出现一次。

返回只出现一次的元素。

要求时间复杂度是 $\text{O(log n)}$，空间复杂度是 $\text{O(1)}$。

示例

示例 1：

输入：$\text{nums = [1,1,2,3,3,4,4,8,8]}$
输出：$\text{2}$

示例 2：

输入：$\text{nums = [3,3,7,7,10,11,11]}$
输出：$\text{10}$

数据范围

• $\text{1}\le \text{nums.length}\le {\text{10}}^{\text{5}}$
• $\text{0}\le \text{nums[i]}\le {\text{10}}^{\text{5}}$

解法一

思路和算法

由于给定的数组已经排序，因此相同元素在数组中一定位于相邻的位置。对于只出现一次的元素，该元素的左边和右边各有偶数个元素。假设只出现一次的元素位于下标 $\text{index}$，考虑下标 $x$ 处的元素，$x\ne \text{index}$。

• 当 $x<\text{index}$ 时，只出现一次的元素在下标 $x$ 的右边。如果 $x$ 是偶数，则 $\text{nums}[x]=\text{nums}[x+1]$；如果 $x$ 是奇数，则 $\text{nums}[x]=\text{nums}[x-1]$。

• 当 $x>\text{index}$ 时，只出现一次的元素在下标 $x$ 的左边。如果 $x$ 是偶数，则 $\text{nums}[x]=\text{nums}[x-1]$；如果 $x$ 是奇数，则 $\text{nums}[x]=\text{nums}[x+1]$。

对于下标 $x$，可以根据 $x$ 的奇偶性以及与 $\text{nums}[x]$ 相同的元素下标判断只出现一次的元素位于下标 $x$ 处、下标 $x$ 的左边或下标 $x$ 的右边。因此可以使用二分查找得到只出现一次的元素的下标。

用 $\text{low}$ 和 $\text{high}$ 分别表示二分查找的下标范围的下界和上界，初始时 $\text{low}$ 和 $\text{high}$ 分别为数组的最小下标和最大下标。每次查找时，取 $\text{mid}$ 为 $\text{low}$ 和 $\text{high}$ 的平均数向下取整，执行如下操作。

• 如果 $\text{mid}$ 是偶数且 $\text{nums}[\text{mid}]=\text{nums}[\text{mid}+1]$，或 $\text{mid}$ 是奇数且 $\text{nums}[\text{mid}]=\text{nums}[\text{mid}-1]$，则只出现一次的元素位于下标 $\text{mid}$ 的右边，因此在下标范围 $[\text{mid}+1,\text{high}]$ 中继续查找。

• 否则，只出现一次的元素位于下标 $\text{mid}$ 或其左边，因此在下标范围 $[\text{low},\text{mid}]$ 中继续查找。

当 $\text{low}=\text{high}$ 时，查找结束，此时 $\text{low}$ 即为只出现一次的元素的下标，$\text{nums}[\text{low}]$ 即为只出现一次的元素。

代码

class Solution {public int singleNonDuplicate(int[] nums) {int low = 0, high = nums.length - 1;while (low < high) {int mid = low + (high - low) / 2;if (mid % 2 == 0 && nums[mid] == nums[mid + 1] || mid % 2 == 1 && nums[mid] == nums[mid - 1]) {low = mid + 1;} else {high = mid;}}return nums[low];}
}

复杂度分析

• 时间复杂度：$O(\log n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。二分查找的范围是数组的全部 $n$ 个下标，二分查找的时间复杂度是 $O(\log n)$。

• 空间复杂度：$O(1)$。

解法二

思路和算法

由于只出现一次的元素的左边有偶数个元素，因此只出现一次的元素一定位于偶数下标，可以只在偶数下标中二分查找。

由于给定的数组长度是奇数，因此数组的最小下标和最大下标都是偶数，二分查找的下标范围的下界和上界的初始值分别为数组的最小下标和最大下标。每次查找时，取 $\text{mid}$ 为 $\text{low}$ 和 $\text{high}$ 的平均数向下取整，如果得到的 $\text{mid}$ 是奇数则将 $\text{mid}$ 减 $1$，确保 $\text{mid}$ 是偶数，执行如下操作。

• 如果 $\text{nums}[\text{mid}]=\text{nums}[\text{mid}+1]$，则只出现一次的元素位于下标 $\text{mid}$ 的右边，因此在下标范围 $[\text{mid}+2,\text{high}]$ 中继续查找。

• 否则，只出现一次的元素位于下标 $\text{mid}$ 或其左边，因此在下标范围 $[\text{low},\text{mid}]$ 中继续查找。

二分查找过程中，每次更新后的下标范围的下界和上界都是偶数，确保只在偶数下标中二分查找。

当 $\text{low}=\text{high}$ 时，查找结束，此时 $\text{low}$ 即为只出现一次的元素的下标，$\text{nums}[\text{low}]$ 即为只出现一次的元素。

代码

class Solution {public int singleNonDuplicate(int[] nums) {int low = 0, high = nums.length - 1;while (low < high) {int mid = low + (high - low) / 2;if (mid % 2 != 0) {mid--;}if (nums[mid] == nums[mid + 1]) {low = mid + 2;} else {high = mid;}}return nums[low];}
}

复杂度分析

• 时间复杂度：$O(\log n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。二分查找的范围是数组的 $\frac{n+1}{2}$ 个偶数下标，二分查找的时间复杂度是 $O(\log n)$。

• 空间复杂度：$O(1)$。