有序数组中的单一元素

本文最后更新于：2024年11月17日 晚上

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

tag:数组 二分查找

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

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

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例 1：

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

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNonDuplicate = function (nums) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (mid % 2 === 1) {
      mid -= 1;
    }

    // 判断mid和mid + 1是否是配对的
    if (nums[mid] === nums[mid + 1]) {
      // 配对在右半部分
      left = mid + 2;
    } else {
      // 配对在左半部分
      right = mid;
    }
  }

  return nums[left];
};

思路：

主要是要满足 O(log n) 时间复杂度和 O(1) 空间复杂度，所以不能使用哈希表。
根据给的条件可知，只有一个数会出现一次，同时看到 O(log n)时间复杂度，就会想到二分查找。

  1. mid 指的下标是偶数的时候，说明左侧是奇数，如果都出现两次的话，那么 nums[mid] === nums[mid+1]，此时说明单一元素在右侧，所以 left = mid + 2
  2. mid 指的下标是奇数的时候，说明左侧是偶数，如果都出现两次的话，那么 nums[mid] === nums[mid-1]，此时说明单一元素在左侧，所以 right = mid
  3. 最后返回 nums[left] 即可

复杂度

时间复杂度：O(log n)

空间复杂度：O(1)