LeetCode笔记：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
限制：
1 <= 数组长度 <= 10000
解法
思路：
- 尝试用
reduce解决，运行以下程序
[0,1,2,3,5,6].reduce((a,b)=>{
console.info(a,b)
return a + 1
})
// 输出
0 1 // 相差1
1 2 // 相差1
2 3 // 相差1
3 5 // 相差2
4 6 // 相差2
我们发现在第一次 b 和 a 相差为 2 的时候，就是我们要找的缺省的数字的位置，即为a+1，这里结果为 4
- 经过测试发现，有两种特殊情况，分别是开头和结尾缺省数字，运行以下程序
缺省 6 的情况
[0,1,2,3,4,5].reduce((a,b)=>{
console.info(a,b)
return a + 1
})
// 输出
0 1
1 2
2 3
3 4
4 5
以及 缺省 0 的情况
[1,2,3,4,5].reduce((a,b)=>{
console.info(a,b)
return a + 1
})
// 输出
1 2
2 3
3 4
4 5
我们发现它们都没有出现 b 和 a 相差为 2 的情况，两个步骤：
- 直接判定数组开头是不是 0，如果不是 0，直接返回缺省值 0
- 下一步遍历数组，查找是否存在
b-a = 2的情况，如果没有，可以判定缺省的数字在数组结尾
代码：
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function (nums) {
// 特殊处理0没有的情况
if (nums[0] !== 0) return 0;
let result = 0;
nums.reduce((a, b) => {
// 第一次相差为2时，a和b中间的数字就是缺省的数字
if (b - a === 2 && result === 0) {
result = a + 1;
}
return a + 1;
});
// result一直等于0，表明b和a没有相差为2过，可以判定缺省的是最后一个数字，取数组长度就是结果值
return result === 0 ? nums.length : result;
};
评论