JS 剑指 Offer 53 - II. 0～n-1中缺失的数字二分法

最新推荐文章于 2022-03-15 14:18:50 发布

gxgalaxy

最新推荐文章于 2022-03-15 14:18:50 发布

阅读量227

点赞数

分类专栏：剑指Offer刷题

本文链接：https://blog.csdn.net/gxgalaxy/article/details/107287914

版权

剑指Offer刷题专栏收录该内容

32 篇文章

订阅专栏

本文介绍了一种使用二分法查找长度为n-1的递增排序数组中缺失的唯一数字的方法。通过对比数组下标与值的关系，快速定位缺失数字的位置。适用于范围0～n-1内有且仅有一个数字不在数组中的情况。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8

二分法

情况1：数组中都是有序的，例如[0,1,2] 那么缺少的是3，这种情况只需要return nums.length
情况2：数组中间有缺失的数字，可以通过二分法找出缺失的数字，根据数组的下标是连续且递增的，通过判断下标和数组每一位的值是否相等找到缺失的值。

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
   var len = nums.length-1;
   if(len === nums[len]) return len+1;
   var left = 0;
   var right = len;
   while(left<=right){
       var mid = parseInt((left+right)/2);
       mid === nums[mid] ? left=mid+1 : right=mid-1;
   }
   return left;
};