题目描述

一个长度为 n-1 的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围 0 ～ n-1 之内。在范围 0 ～ n-1 内的 n 个数字中有且只有一个数字不在该数组中,请找出这个数字

题目描述

• 数字唯一
• 缺失其中一个

参数说明

/**
 * @param {number[]} nums
 * @return {number}
 */

题解及实现

1. 二分查找

用两指针,i 指针指向最后一位,j 指针指向第一位,考虑到只有一个数字缺失,例如[1,2,3,4],取中点 i+j/2 = 1.5 无论取 1,还是 2,与对应位数字相比都是小的,这说明小数缺失,大数左移,所以将搜索范围缩小至[j,mid-1],此例子中 j==i==0,最后比较此位,若 i>nums[i],说明大数缺失,反之小数缺失

var missingNumber = function (nums) {
  let i = nums.length - 1;
  let j = 0;
  let mid;
  while (j <= i) {
    mid = Number.parseInt((i + j) / 2);
    mid === nums[mid] ? (j = mid + 1) : (i = mid - 1);
  }
  return j; //最后j指向的索引就是结果
};

时间复杂度:O(log(n))

• 资源使用情况
  • 执行用时：84 ms, 在所有 JavaScript 提交中击败了 81.44%的用户
  • 内存消耗：40.1 MB, 在所有 JavaScript 提交中击败了 6.47%的用户

2. 遍历总和作减法

考虑到数字唯一且只缺失一个,可以将数组中的整数进行累加再被本来应该的总数减

var missingNumber = function (nums) {
  return (
    (nums.length * (nums.length + 1)) / 2 - nums.reduce((a, b) => a + b, 0)
  );
};

时间复杂度:O(n)

• 资源使用情况
  • 执行用时：76 ms, 在所有 JavaScript 提交中击败了 95.33%的用户
  • 内存消耗：39.7 MB, 在所有 JavaScript 提交中击败了 13.25%的用户
    问题:太慢了

同思路黑科技版

var missingNumber = function (nums) {
  return (nums.length * (nums.length + 1)) / 2 - eval(nums.join("+"));
};

• 资源使用情况
  • 执行用时：112 ms, 在所有 JavaScript 提交中击败了 8.04%的用户
  • 内存消耗：41 MB, 在所有 JavaScript 提交中击败了 5.03%的用户
    问题:黑科技是用来炫技的,不是拿来用的

3. 数学思维之异或

众所周知,相同的数异或为 0,如果将数组补全为 n 为,比如[0,1,2,3,4],那么其和相应索引之间异或再相加为 0,现缺失了一个数,但我们把索引补全,比如上述缺失 1,但索引补全为 0,1,2,3,4 他们和数组元素进行异或的和就是 1

var missingNumber = function (nums) {
  let i = 0;
  let result = 0;
  for (; i < nums.length; i++) result ^= i ^ nums[i];
  return result ^ nums.length;
};

时间复杂度:O(n)

• 资源使用情况
  • 执行用时：80 ms, 在所有 JavaScript 提交中击败了 90.78%的用户
  • 内存消耗：39.9 MB, 在所有 JavaScript 提交中击败了 10.86%的用户