剑指 Offer 53 - II. 0～n-1中缺失的数字(javascript解法)

叁歲伎倆 2022-10-29 05:18 79阅读 0赞

###### 一、题目描述 ######

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

###### 二、示例 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70]

###### 三、解题思路 ######

1.  我的第一个思路是直接进行暴力的匹配 看哪个的值和下标不一致，直接输出，刚开始的时候会疏忽一个问题就是缺失最后一个的情况，所以需要给数组的最后加上任意的一个值，方便进行比较！
2.  二分法的思路进行比较

> 可以先进行左右两边的分别比较来缩小比较的范围![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70 1]

###### 四、代码展示 ######

/** * @param {number[]} nums * @return {number} */
    var missingNumber = function(nums) { 
        nums.push('x')
        let n = nums.length 
        for(let i = 0 ; i < n ; i++){ 
             if(nums[i]!==i){ 
                return i 
            }
        }
    
    };
    
    
    /** * @param {number[]} nums * @return {number} */
    var missingNumber = function(nums) { 
        let left = 0,
            right = nums.length - 1;
        while (left <= right) { 
            let mid = Math.floor((left + right) / 2);
            if (mid === nums[mid]) { 
                left = mid + 1;
            } else if (mid < nums[mid]) { 
                right = mid - 1;
            }
        }
    
        return left;
    };

###### 五、结果 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70]: /images/20221024/c6575367275d4d0c9d21ed0f49040b42.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70 1]: /images/20221024/2be11a85e5ef43429393ccd6c3d64480.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70 2]: /images/20221024/ad4b2d8c9228414fb31895a740ee182f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70 3]: /images/20221024/28929aa0950d49219b7fa0ae40b4720d.png