一道头条面试题，差点没读懂题目，找出数组中缺失的数字,最近击败100%的用户！
题目
一个长度为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
来源：力扣（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 ）都没有和数组下标对齐。 所以现在我们知道了数组是上图中的这个样子，知道了数组是这个样子，那我们就简单了呀~
暴力解法
暴力解法图解
暴力动画
代码
class 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
class 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++
class Solution {
public:
int missingNumber(vector& 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
/**
* @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
class 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
评论