Pengjielee's blog

题目

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例 1:
输入: [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:
输入: [3,3,7,7,10,11,11]
输出: 10

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

1、位运算

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNonDuplicate = function (nums) {
  let result = nums[0];

  for (let i = 1; i < nums.length; i++) {
    result = result ^ nums[i];
  }

  return result;
};

2、二分搜索

我们的数组个数始终是奇数，因为有一个元素出现一次，其余元素出现两次。

var singleNonDuplicate = function (nums) {
  let low = 0,
    high = nums.length - 1;

  while (low < high) {
    // 获取中间的元素下标
    const mid = low + Math.floor((high - low) / 2);
    // 右半部分是偶数
    const rightHalvesAreEven = (high - mid) % 2 === 0;
    // 中间元素的右边是同一元素
    if (nums[mid + 1] === nums[mid]) {
      if (rightHalvesAreEven) { //[1,1,4,4,(5),5,6,8,8]
        low = mid + 2;
      } else {  //[1,1,4,5,5,(6),6,8,8,9,9]
        high = mid - 1;
      }
    } else if (nums[mid - 1] === nums[mid]) { // 中间元素的左边是同一元素
      if (rightHalvesAreEven) { //[1,1,4,5,(5),6,6,8,8]
        high = mid - 2;
      } else {  //[1,1,4,4,5,(5),6,6,8,9,9]
        low = mid + 1;
      }
    } else {
      return nums[mid];
    }
  }
  return nums[low];
};