問題

一個(gè)從0開始的連續(xù)數(shù)列(比如[0 .. n])，去除i個(gè)數(shù)，然后打亂順序，該怎樣找回這i個(gè)數(shù)

測(cè)試

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))，總共時(shí)間復(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)的時(shí)間復(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
}

只有一個(gè)missing number的特殊情況

將所有應(yīng)該存在的數(shù)相加，再減去現(xiàn)在的數(shù)列之和，得到丟失的唯一一個(gè)數(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
}