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

🟠   🔖  数组 二分查找  🔗 力扣 LeetCode

题目

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.

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]

Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11]

Output: 10

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5

题目大意

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

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

你设计的解决方案必须满足 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^5
• 0 <= nums[i] <= 10^5

解题思路

由于数组是有序的，我们可以利用二分查找来解决问题，具体分析如下：

1. 观察规律，每个元素出现两次，且数组是严格有序的：

   • 假设所有元素都成对出现，则它们的索引呈现如下模式：成对元素的第一个位置为偶数，第二个位置为奇数。
   • 例如，数组 [1, 1, 2, 2, 3, 3, 4] 中，元素成对的索引关系是 (0, 1), (2, 3), (4, 5)。
   • 如果某个元素只出现一次，则从它之后，所有成对的索引模式将被打破。
   • 例如，数组 [1, 1, 2, 3, 3, 4, 4] 中，2 只出现一次，从索引 2 开始，索引模式变为奇数偶数。

2. 我们可以通过二分查找定位唯一的数字：

   • 取中间索引 mid。
   • 检查 mid 是否满足成对规律：
     • 如果 mid 是偶数，且 nums[mid] == nums[mid + 1]，说明唯一的数字在右半部分。
     • 如果 mid 是奇数，且 nums[mid] == nums[mid - 1]，说明唯一的数字在右半部分。
     • 否则，唯一的数字在左半部分。
   • 通过调整二分查找的范围 left 和 right，逐渐缩小范围，最终找到唯一的数字。

复杂度分析

• 时间复杂度：O(log n)，每次查找范围缩小一半。
• 空间复杂度：O(1)，使用了常数个额外变量。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNonDuplicate = function (nums) {
	let left = 0,
		right = nums.length - 1;
	let idx;
	while (left <= right) {
		const mid = Math.floor((left + right) / 2);
		// 检查是否在成对索引模式下
		if (
			(mid % 2 === 0 && nums[mid] === nums[mid + 1]) ||
			(mid % 2 === 1 && nums[mid] === nums[mid - 1])
		) {
			// 唯一元素在右边
			left = mid + 1;
		} else {
			// 唯一元素在左边或当前
			idx = mid;
			right = mid - 1;
		}
	}
	return nums[idx];
};