[JavaScript 刷题] 二分搜索 - 有序数组的 Single Element,Leetcode 540

[JavaScript 刷题] 二分搜索 - 有序数组的 Single Element,Leetcode 540

题目地址:540. Single Element in a Sorted Array

题目

如下:

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Follow up: Your solution should run in O ( l o g n ) O(log n) O(logn) time and O ( 1 ) O(1) O(1) space.

解题思路

这道题其实第一眼看上去很奇怪,因为题目的要求是:在一堆出现了两次的元素中,找出 唯一一个出现了一次的 元素。而且题目的提示就是时间复杂度为 O ( l o g n ) O(log n) O(logn),空间复杂度为 O ( 1 ) O(1) O(1),也就是说必须要用二分搜索。

传统二分搜索应用的范围是查询某一个数字是否出现在数组中。在其他的数字都是成双出现,仅有一个单独数字时,这就意味着数组的长度永远都是奇数。也因此,通过从中间将数组截取为两截,就可以判断单独的数字出现在那一截——它只会出现在长度为奇数的那一截。

下面的案例中,中位数的背景颜色被标注为黄色,要寻找的数字标记为红色。

这里总共会标记 5 个案例,分别对应可能出现的 5 种情况。

    案例 1,当数字正好出现在中间时,红+黄=橘,所以这里会使用橘色标注

    1 1 2 3 3

    这种情况下也就意味着 a r r [ m i d ] ≠ a r r [ m i d + 1 ] arr[mid] \ne arr[mid+1] arr[mid]​=arr[mid+1] 和 a r r [ m i d ] ≠ a r r [ m i d − 1 ] arr[mid] \ne arr[mid-1] arr[mid]​=arr[mid−1],也就可以直接返回了。

    案例 2,当中位数是偶数,并且当要寻找的数字出现在前半截时:

    1 1 2 3 3 4 4 8 8

    这时候的 h i = m i d − 2 hi = mid - 2 hi=mid−2,截取的部分为:

    1 1 2

    案例 3,当中位数是偶数,并且当要寻找的数字出现在后半截时:

    1 1 2 2 3 3 4 8 8

    这时候的 l o = m i d + 2 lo = mid + 2 lo=mid+2,截取的部分为:

    4 8 8

    案例 4,当中位数是奇数,并且当要寻找的数字出现在前半截时:

    3 7 7 10 10 11 11

    这时候的 h i = m i d − 1 hi = mid - 1 hi=mid−1,截取的部分为:

    3 7 7

    案例 5,当中位数是奇数,并且当要寻找的数字出现在后半截时:

    3 3 7 7 10 11 11

    这时候的 l o = m i d + 1 lo = mid + 1 lo=mid+1,截取的部分为:

    10 11 11

因此,可以利用 奇偶数 这一个特性,去解决这个问题。

使用 JavaScript 解题

其实可以再简化一下,不过下面这个版本就是完全按照上面的解题思路写的,用了两层 if-else 进行嵌套:

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNonDuplicate = function (nums) {
  let lo = 0,
    hi = nums.length - 1,
    mid;
  while (lo <= hi) {
    mid = Math.floor((lo + hi) / 2);
    // 前后均不相等,找到了对应数字了
    if (nums[mid] !== nums[mid + 1] && nums[mid] !== nums[mid - 1])
      return nums[mid];
    // 代表前一个部分数组长度为奇数
    if (mid % 2 === 0) {
      // 通过判断前后的数字是否与当前数字相同去选择要截取的部分
      if (nums[mid] === nums[mid - 1]) {
        hi = mid - 2;
      } else if (nums[mid] === nums[mid + 1]) {
        lo = mid + 2;
      }
    }
    // 代表后一部分数组长度为奇数
    else {
      // 同样通过判断前后的数字是否与当前数字相同去选择要截取的部分
      if (nums[mid] === nums[mid - 1]) {
        lo = mid + 1;
      } else if (nums[mid] === nums[mid + 1]) {
        hi = mid - 1;
      }
    }
  }
  return nums[lo];
};

console.log(singleNonDuplicate((nums = [1, 1, 2, 3, 3, 4, 4, 8, 8])));
console.log(singleNonDuplicate((nums = [3, 3, 7, 7, 10, 11, 11])));

果然是一道 Medium 的题目,解决起来比 Easy 要稍微难一些。

来源url
栏目