leetcode 算法题268 (简单072) 缺失数字

• 题目介绍

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，
找出 0 .. n 中没有出现在序列中的那个数。

• 示例

输入: [3,0,1]
输出: 2

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

• 解法一

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
  if(nums.length === 0) {
      return 0;
  }
  if(nums.length === 1) {
      return nums[0] === 0 ? nums.length : 0;
  }
  nums.sort((n1, n2) => n1 - n2)
  console.log(nums);
  let i = nums.length - 1;
  while(i > 0) {
    if(nums[i] - nums[i - 1] !== 1) {
      return nums[i] - 1;
    }
    i--;
  }
 return nums[0] === 0 ? nums.length : 0;
};

执行用时 : 176 ms, 在所有 JavaScript 提交中击败了16.64%的用户

内存消耗 : 38.9 MB, 在所有 JavaScript 提交中击败了5.88%的用户

• 解法二

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
  let temp = new Array(nums.length + 1), i = 0;
  while(i < nums.length) {
    temp[nums[i++]] = 1
  }
  while(i >= 0) {
    if(temp[i] !== 1) {
      return i;
    }
    i--;
  }
};

执行用时 : 80 ms, 在所有 JavaScript 提交中击败了92.55%的用户

内存消耗 : 37.1 MB, 在所有 JavaScript 提交中击败了35.39%的用户

• 解法三

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
  let i = 0, j = 0;
  while (j < nums.length) {
    if (nums[j] !== i) {
      j++;
    } else {
      i++;
      j = 0;
    }
  }
  return i;
};

执行用时 : 296 ms, 在所有 JavaScript 提交中击败了11.61%的用户

内存消耗 : 36.4 MB, 在所有 JavaScript 提交中击败了42.98%的用户

• 解法四

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
  let i = 0, num = 0;
  while (i < nums.length) {
    num ^= (i ^ nums[i++]);
  }
  return num ^ i;
};

执行用时 : 76 ms, 在所有 JavaScript 提交中击败了96.19%的用户

内存消耗 : 36 MB, 在所有 JavaScript 提交中击败了72.40%的用户