剑指 Offer 53 - II. 0～n-1中缺失的数字【5】

╰半夏微凉° 2023-09-26 10:43 45阅读 0赞

> **难度等级：中等**

> **上一篇算法：**
> 
> [ 剑指 Offer 53 - I. 在排序数组中查找数字 I【数组】][_ Offer 53 - I. _ I]

> **力扣此题地址：**
> 
> [剑指 Offer 53 - II. 0～n-1中缺失的数字 - 力扣（LeetCode）][Offer 53 - II. 0_n-1_ - _LeetCode]

## 1.题目：0～n-1中缺失的数字 ##

一个长度为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

## 2.解题思路： ##

> **利用二分查找**
> 
> 首先数组0-n-1中数值是有序的，只有其中一个数不在数组中，设它为m，则m之前的数值与下标都是相等的，m之后的数值都比下标大1，即m+1、m+2......
> 
> 二分法求解
> 
> （1）中间元素值等于下标元素，则目标对象在后半部分
> 
> （2）中间元素值不等于下标元素，则目标对象在前半部分
> 
> 接着不断二分下去，直到找到元素。

## 3.代码实现： ##

class Solution {
        public int missingNumber(int[] nums) {
    
            // left 指向当前区间的最左边位置，所以初始化为 0
            int left = 0 ;
    
            // right 指向当前区间的最右边位置，所以初始化为 nums.length - 1
            int right = nums.length - 1;
    
            // 循环进行二分查找，直到左端点位置超过了右端点
            while( left <= right ) {
    
                // 计算当前区间的中间位置，向下取整
                int mid = (left + right) / 2;
    
                // 如果中间位置的元素值等于当前索引的值
                // 那么说明从 left 到 mid 的这些元素都在正确的位置上
                // 即从 left 到 mid 的这些数字都在数组中，没有发生缺失
                // 所以需要在 mid + 1 到 right 这个区间去查找缺失的数字
                if(nums[mid] == mid){
    
                    // 缩小范围为 mid + 1 到 right
                    // 当前区间的左侧为 left = mid + 1，右侧 right 
                    left = mid + 1;
    
                // 否则，说明从 left 到 mid 的这些元素，有元素不在正确的位置上
                // 即从 left 到 mid 的这些数字有数字发生缺失
                // 所以需要在 left 到 mid - 1 这个区间去查找缺失的数字
                }else{
    
                    // 所以缩小范围为 left 到 mid - 1
                    // 当前区间的左侧为 left，右侧 right = mid - 1
                    right = mid - 1;
    
                }
            }
    
            // 由于只有一个数字缺失，所以找到的时候，left 指向的那个数字就是，使得后面所有数字与索引不一一对应时的第一个数字
            // 返回就行
            return left;
        }
    }

## 4.知识点补充： ##

[ 二分法查找（折半查找）][Link 1]

[_ Offer 53 - I. _ I]: https://blog.csdn.net/m0_51697147/article/details/127225990?spm=1001.2014.3001.5502
[Offer 53 - II. 0_n-1_ - _LeetCode]: https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/comments/
[Link 1]: https://blog.csdn.net/m0_51697147/article/details/124911763