题目
一个长度为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
2
3
4来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
分析这道题的题目
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
这道题目的本质：小夕认为是需要读懂题目。小夕一开始也没被整懵了，后来想了想原来是这么回事：
这道题题目本质是找到第一个数组下标和数组中的数不匹配的，如下图中的例子，是数组下标为4的时候，数组中的数应该是4。
为什么是这样子呢？
阅读题目，数组是单调递增的，而且数字是无重复的，所以缺失一个数字的话，就导致数组的下标和数组的数字没对应上。
如数组下标4，而且从数组下标4开始到之后的所有的数组下标（4/5/6）中的数（数组中的5/6/7 ）都没有和数组下标对齐。
所以现在我们知道了数组是上图中的这个样子，知道了数组是这个样子，那我们就简单了呀~
暴力解法
暴力解法图解
暴力动画
代码
1
2
3
4
5
6
7
8
9
10
11
12class Solution { public int missingNumber(int[] nums) { for(int i = 0; i < nums.length; i ++) { if(nums[i] != i) { return i; } } return nums.length; } }
二分查找
由于是排序数组，肯定会想到二分查找：
1.首先数组里的元素都是固定的，我们只需要通过二分查找确定缺失的元素是在左边还是右边。
2.老样子 left = 0 和 right = nums.length -1
3.我们先通过计算获取到中位数int mid = left + (right -left) / 2
4.判断nums[mid] == mid 虽然数组元素是缺失的 但是下标是完整，如果 nums[mid] == mid 说明缺失的元素在右边，否则相反。
5.当我们判断缺失的元素在右边时候，这时候区间就是[mid + 1,right];
6.当我们判断缺失的元素在左边时候，这时候区间就是[left,mid - 1];
7.当left指向了右边数组的第一个元素 right指向了做数组的最后一个元素则直接返回left。
为了更好的理解，图解看一下：
图解
二分查找动画
代码
Java
1
2
3
4
5
6
7
8
9
10
11
12class Solution { public int missingNumber(int[] nums) { int i = 0, j = nums.length - 1; while(i <= j) { int m = (i + j) / 2; if(nums[m] == m) i = m + 1; else j = m - 1; } return i; } }
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution { public: int missingNumber(vector<int>& nums) { int left = 0, right = nums.size(); //使用左闭右开区间 while(left < right) { int mid = (right - left)/2 + left; if(nums[mid] != mid) right = mid; if(nums[mid] == mid) left = mid+1; } return left; } };
JS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20/** * @param {number[]} nums * @return {number} */ var missingNumber = function(nums) { // 左指针 let leftI = 0 // 右指针 let rightI = nums.length // 中间指针 let midI // 以 leftI < rightI 为条件遍历数组 while(leftI <= rightI){ midI = Math.floor((leftI + rightI)/2) // 如果 nums[midI] === midI 说明想寻找的数在 midI 右方 nums[midI] === midI ? leftI = midI + 1 : rightI = midI - 1 } return leftI };
Python
1
2
3
4
5
6
7
8
9class Solution: def missingNumber(self, nums: List[int]) -> int: i, j = 0, len(nums) - 1 while i <= j: m = (i + j) // 2 if nums[m] == m: i = m + 1 else: j = m - 1 return i
最后
以上就是开放发箍最近收集整理的关于一道头条面试题，小夕差点没读懂题目，找出数组中缺失的数字,最近击败100%的用户！...题目分析这道题的题目暴力解法二分查找代码的全部内容，更多相关一道头条面试题，小夕差点没读懂题目，找出数组中缺失内容请搜索靠谱客的其他文章。
![[剑指offer] 数组中重复的数字](/uploads/reation/bcimg12.png)
发表评论 取消回复