Given an array containing n distinct numbers taken from 0, 1, 2, ..., n,
find the one that is missing from the array.
input: 一串數字陣列
output: 找出消失的那個
Example 1:
Input: [3,0,1]
Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note:
Your algorithm should run in linear runtime complexity.
Could you implement it using only constant extra space complexity?
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
};
怎麼解
第一個想法是先排序後前後比對，但這樣會用到 時間複雜度 Big O (n²)，
其實可以先算出總長度，再減掉 input 就可以找到消失那個值！以 [3, 0, 1] 來說，
我一開始就會知道 length = 3，所以總和是 (1+3)*3/2 = 6
6 - 3 - 0 - 1 = 2，所以是 2 消失了
var missingNumber = function(nums) {
let len = nums.length
let correctSum = (1 + len)*len/2
let currentSum = nums.reduce((a, b) => a + b);
return correctSum - currentSum;
};