問題
一個從0開始的連續(xù)數(shù)列(比如[0 .. n])艺演，去除i個數(shù)实牡，然后打亂順序分飞，該怎樣找回這i個數(shù)
測試
var findMissingNums = require("./findMissingNums.js")
var missing = [213,345,900]
var arr = Array.apply(null, new Array(1000)).map(function(val, idx){return idx})
missing.forEach(function(val){
var pos = arr.indexOf(val)
if (~pos) {
arr.splice(pos, 1)
}
})
arr.sort(function(){return Math.random() - 0.5})
describe("find the missing numbers", function(){
expect(findMissingNums(arr)).to.eql([213, 345, 900])
})
統(tǒng)一解法
先將這被打亂的數(shù)列排序(O(nlogn))悴务，再用依次查找丟失的數(shù)字(O(n))，總共時間復(fù)雜度為(O(nlogn))
function findMissingNums(arr){
var arrClone = arr.slice(0)
var ret = []
arrClone.sort(function(a, b){return a-b}).reduce(function(pre, cur, idx){
if ((cur - pre) === 1) {
return cur
} else {
ret.push(cur - 1)
return cur
}
})
return ret
}
使用hash表
把object看作hash表譬猫，實(shí)現(xiàn)的時間復(fù)雜度為(O(n))
function findMissingNums(arr){
var hash = {}
var maxNum = -1
arr.forEach(function(val){
hash[val] = true
if (val > maxNum) {
maxNum = val
}
})
var i, ret = []
for (i = 0; i < maxNum; ++i) {
if (hash[i] === undefined) {
ret.push(i)
}
}
return ret
}
只有一個missing number的特殊情況
將所有應(yīng)該存在的數(shù)相加，再減去現(xiàn)在的數(shù)列之和羡疗，得到丟失的唯一一個數(shù)染服。這里，我們用xor來代替加法
function findOnlyMissingNum(arr, length){
var i
var X = Y = 0
for (i = 0; i < length; ++i) {
X ^= i
}
for (i = 0; i < arr.length; ++i) {
Y ^= arr[i]
}
return X ^ Y
}
