算法：查找丢失的整数

问题

一个从0开始的连续数列(比如[0 .. n])，去除i个数，然后打乱顺序，该怎样找回这i个数

测试

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])
})

统一解法

先将这被打乱的数列排序(O(nlogn))，再用依次查找丢失的数字(O(n))，总共时间复杂度为(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表，实现的时间复杂度为(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的特殊情况

将所有应该存在的数相加，再减去现在的数列之和，得到丢失的唯一一个数。这里，我们用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
}