15. 缺失的数字

RT

提供两个Scala版本,第一个是Java版的复制,第二个是Scala Stype:

  // Time: O(n), Space: O(1)
  def missingNumber(nums: Iterable[Int]): Int = {
    require(nums.nonEmpty)
    var result = nums.size // 最大值
    var i = 0
    val iter = nums.iterator
    while (iter.hasNext) {
      result = result ^ i ^ iter.next()
      i += 1
    }
    result
  }

  def missingNumberScala(nums: Iterable[Int]): Int = {
    require(nums.nonEmpty)
    nums.reduce(_ ^ _) ^ Iterator.from(0).take(nums.size + 1).reduce(_ ^ _)
  }