有序数组中的单一元素

题目

给你一个仅由整数组成的有序数组, 其中每个元素都会出现两次, 唯有一个数只会出现一次. 请你找出并返回只出现一次的那个数. 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度.

提示:

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

示例

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

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

题解

记这个单独出现的数字为 x, 那么如果保证其它每个元素都会出现两次且有序, 说明 x 左边和右边都是偶数个. 以示例一为例, 2 左边有 2 个, 2 右边有 6 个.

我们如果暂且不考虑这个单独数元素, 即变成 [1, 1, 3, 3, 4, 4, 8, 8], 可以发现相同元素数对的第一个元素索引一定是偶数, 第二个元素元素索引一定是奇数. 而插入这个元素后, 它的左边部分仍然是第一个元素索引是偶数, 第二个元素元素索引是奇数, 而右边则反了过来, 变成 第一个元素索引是奇数, 第二个元素元素索引是偶数.

所以对于 mid 值:

• 如果 mid 是偶数, 如果没有单独元素的, 它应该和它右边那个元素相等, 如果相等, 说明单独元素在 mid + 1 右边, 否则在 mid 左边
• 如果 mid 是奇数, 如果没有单独元素的, 它应该和它左边那个元素相等, 如果相等, 说明单独元素在 mid + 1 右边, 否则在 mid 左边

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNonDuplicate = function (nums) {
  const n = nums.length
  let low = 0,
    high = n - 1

  while (low < high) {
    const mid = Math.floor(low + (high - low) / 2)

    if (mid % 2 === 0) {
      if (mid + 1 < n && nums[mid] == nums[mid + 1]) {
        low = mid + 1
      } else {
        high = mid
      }
    } else {
      if (mid - 1 >= 0 && nums[mid - 1] == nums[mid]) {
        low = mid + 1
      } else {
        high = mid
      }
    }
  }

  return nums[high]
}

JavaScript - 位运算

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNonDuplicate = function (nums) {
  const n = nums.length
  let low = 0,
    high = n - 1

  while (low < high) {
    const mid = Math.floor(low + (high - low) / 2)

    if (nums[mid] === nums[mid ^ 1]) {
      low = mid + 1
    } else {
      high = mid
    }
  }

  return nums[high]
}

Rust

pub fn single_non_duplicate(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let (mut low, mut high) = (0, n - 1);

    while low < high {
        let mid = low + (high - low) / 2;

        if nums[mid] == nums[mid ^ 1] {
            low = mid + 1
        } else {
            high = mid
        }
    }

    nums[high]
}