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

题目链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/

本文提供JavaScript解法：1、迭代、数组下标应用 　　2、二分搜索（折半查找）【更优】

1、迭代、数组下标应用

题目部分内容：在一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。

也就是说递增的数字之间最大差值为1，要用数组元素值作为下标来记录是不占多大空间的。

思路：

遍历数组，将存在的数记录下来；记录手段是将数组元素值作为临时数组的下标，若存在则记为1；

遍历完成后查找临时数组中值不为1的下标便是数组缺失的数。

时间复杂度：O(N)　　空间复杂度：O(N)

 1 /**
 2  * @param {number[]} nums
 3  * @return {number}
 4  * 要点：以nums数组的元素值作为临时数组的下标（临时数组的下标与nums数组元素对应）
 5  */
 6 var missingNumber = function (nums) {
 7   if (nums == null) return nums;
 8   let array = [];
 9   let length = nums.length;
10   for (let i = 0; i < length; i++) {
11     // 记录nums数组中存在的元素
12     array[nums[i]] = 1;
13   }
14   // 返回值不为1的下标
15   let maybeRsult = array.findIndex((element) => element !== 1);
16   // 处理[0, length)都存在的情况（也就是nums中不存在元素length的情况）
17   return maybeRsult !== -1 ? maybeRsult : length;
18 };

2、二分搜索（折半查找）【更优】

思路：排序数组中的搜索问题，应该首先想到 二分法解决。

参考：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/solution/mian-shi-ti-53-ii-0n-1zhong-que-shi-de-shu-zi-er-f/  

时间复杂度：O(log N)，二分法为对数级别复杂度

空间复杂度：O(1) ，几个变量使用常数大小的额外空间

 1 /**
 2  * @param {number[]} nums
 3  * @return {number}
 4  * 缺值可能存在三个地方：1.left子数组 2.right子数组 3.mid
 5  * 判断位置：下标是否等于下标对应的值（mid === nums[mid]）
 6  * 若等：
 7  * 缺值可能存在right子数组
 8  * 否则（也就是mid > nums[mid], 根据题，不可能存在mid < nums[mid]的情况）：
 9  * 缺值可能存在left子数组、mid中
10  */
11 var missingNumber = function (nums) {
12   if(nums == null) return nums;
13   let left = 0, right = nums.length -1;
14   while(left <= right) {
15     // 由于JavaScript没有整型、浮点之分，下行代码算出的结果可能会是浮点数。因此会出错。
16     // let mid = left + (right - left) / 2;
17     // Math.trunc() 方法会将数字的小数部分去掉，只保留整数部分。
18     let mid = Math.trunc(left + (right - left) / 2);
19     if(mid === nums[mid]) left = mid + 1;
20     else right = mid - 1;
21   }
22   return left;
23 };