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

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

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

题目

示例 1

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

示例 2

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

答案

二分法

^的运算法则： 只有在两个比较的位不同时其结果是 1，否则结果为 0 即“两个输入相同时为 0，不同则为 1”！

思路：

1. 声明对撞指针 left/right

2. 根据二分法比较 target，找到对应下标 mid

   • while 循环条件： while (left <= right) {}
   • nums[mid]对比nums[mid ^ 1]
   • 相等则 left = mid + 1
   • 不相等 right = mid

var singleNonDuplicate = function(nums) {

  let left = 0
  let right = nums.length -1

  // 常规二分法，不断取【中间值】去尝试。
  // 直到left <= right 的值为止，说明中间值只剩一个，无法继续二分
  while (left < right) {
    // 动态取中间:
    let mid=left+Math.floor((right-left)/2);

    // 满足条件：当前元素【中间值】等于下一项，说明找到问题元素，记录下标
    if(nums[mid] == nums[mid ^ 1]){
      left = mid + 1
    }else{ // 不满足：继续二分
      right = mid
    }
    /*
      console.log('mid',mid,'left',left,'right',right)

      mid 4 left 0 right 4
      mid 2 left 0 right 2
      mid 1 left 0 right 1
      mid 0 left 1 right 1
    */
  }

    return nums[left]
};

var nums = [1,1,2,3,3,4,4,8,8]

console.log(singleNonDuplicate(nums))

暴力

var singleNonDuplicate = function (nums) {
    //排序后直接两两比较
    nums = nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i += 2) {
        if (nums[i] != nums[i + 1]) return nums[i];
    }
};

var nums = [1,1,2,3,3,4,4,8,8]

console.log(singleNonDuplicate(nums))