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

你的名字 2022-09-08 10:27 112阅读 0赞

此题目可以跟这个题对照着看：[https://blog.csdn.net/qq\_35354855/article/details/119906864][https_blog.csdn.net_qq_35354855_article_details_119906864]

> 一个长度为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 <= 数组长度 <= 10000
> 
> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

同样是将数组分成两部分来看，即左数组右数组，找到右数组的首位元素就可以了。

class Solution {
        public int missingNumber(int[] nums) {
            int i = 0, j = nums.length-1;
            int m = (i + j)/2;
            while(i <= j){
                if(nums[m] == m){ i = m + 1;}
                else { j = m - 1; }
                m = (i + j) / 2;
            }
            return  i;
        }
    }

① 当nums\[m\] == m的时候，这时nums\[m\] 在左数组，所以使 i = m + 1，然后重新计算m

② 当nums\[m\] != m的时候，这时nums\[m\] 肯定在右数组，但不确定是右数组第一个还是第几个，所以 j = m - 1，然后重新计算m

③ 假设当nums\[m\] != m的时候，m为右数组第一个元素，此时 j = m - 1，j 去到了左数组中，那么接下来m肯定是判断为nums\[m\] == m，即 i = m + 1，直到 i > j为止。

此时右数组第一个元素为nums\[i\]，所以此时返回 i。

--------------------

学习完之后，一定要立刻检测自己是否学会了，学完之后要练，要检测和输出。

如果你一道题目一道题目地去做，然后过了几天又看了一下，还是不会，这是什么情况呢？

是当时就没搞清楚每个细节，还是只是背下来了代码，根本没理解？

这时候就该根据自己的问题进行学习方式的调整了，

通过不断分析、反思、调整、应用，

来弄清楚自己是如何学习的，什么样的学习方法最适合自己，来达到最佳的学习效果。

[https_blog.csdn.net_qq_35354855_article_details_119906864]: https://blog.csdn.net/qq_35354855/article/details/119906864