78 - 缺失数字

题目

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

输入: [3,0,1] 输出: 2

示例 2:

输入: [9,6,4,2,3,5,7,0,1] 输出: 8

说明: 你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

解答

这题目问题很大。。不过leetcode题目一向如此。。

给一个数组，长度是n，其元素内容是打乱的从0到n，但里面缺了一个数，求那个数。

第一反应就是要排序咯

排序

js的这个nums.sort()，问题很大。。

输入：

[45, 35, 38, 13, 12, 23, 48, 15, 44, 21, 43, 26, 6, 37, 1, 19, 22, 3, 11, 32, 4, 16, 28, 49, 29, 36, 33, 8, 9, 39, 46, 17, 41, 7, 2, 5, 27, 20, 40, 34, 30, 25, 47, 0, 31, 42, 24, 10, 14]

输出：

nums [

0, 1, 10, 11, 12, 13, 14, 15, 16, 17, 19,

2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,

3, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39,

4, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,

5, 6, 7, 8, 9

]

？？？说好的排序呢？

查了资料后发现，原来是因为一些历史原因，用了不稳定的快速排序算法。而且sort数字的时候，都要先toString()变成字符串再根据ascii码排序。

解决方法就是加一个字段。

var missingNumber = function (nums) {
  nums.sort((a, b) => a - b)
  if (nums[0] != 0) {
    return 0
  }
  if (nums[nums.length - 1] != nums.length) {
    return nums.length
  }
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] != nums[i - 1] + 1) {
      return nums[i - 1] + 1
    }
  }
  return -1
};

Runtime: 92 ms, faster than 23.00% of JavaScript online submissions for Missing Number.

Memory Usage: 37.7 MB, less than 17.14% of JavaScript online submissions for Missing Number.

go的sort包就好多了😂，起码不会搞这种幺蛾子

func missingNumber(nums []int) int {
    sort.Ints(nums)
    if nums[0] != 0 {
        return 0
    }
    if nums[len(nums)-1] != len(nums) {
        return len(nums)
    }
    for i := 1; i < len(nums); i++ {
        if nums[i] != nums[i-1]+1 {
            return nums[i-1] + 1
        }
    }
    return -1
}

Runtime: 32 ms, faster than 9.59% of Go online submissions for Missing Number.

Memory Usage: 5.9 MB, less than 100.00% of Go online submissions for Missing Number.

换一种排序方法会不会快一些呢？

func missingNumber(nums []int) int {
    sort.Slice(nums, func(i, j int) bool {
        return nums[i] < nums[j]
    })
    ...
}

Runtime: 24 ms, faster than 28.22% of Go online submissions for Missing Number.

Memory Usage: 5.9 MB, less than 100.00% of Go online submissions for Missing Number.

快了一点点😂

哈希表

var missingNumber = function (nums) {
  const map = new Map()
  for (let i = 0; i < nums.length; i++) {
    map.set(nums[i], 1)
  }
  for (let i = 0; i < nums.length + 1; i++) {
    if (!map.has(i)) {
      return i
    }
  }
  return -1
};

Runtime: 84 ms, faster than 27.72% of JavaScript online submissions for Missing Number.

Memory Usage: 39.9 MB, less than 5.72% of JavaScript online submissions for Missing Number.

比排序稍微快一点点。

func missingNumber(nums []int) int {
    data := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        data[nums[i]] = 1
    }
    for i := 0; i < len(nums)+1; i++ {
        if _, ok := data[i]; !ok {
            return i
        }
    }
    return -1
}

Runtime: 28 ms, faster than 18.08% of Go online submissions for Missing Number.

Memory Usage: 6.7 MB, less than 100.00% of Go online submissions for Missing Number.

骚操作之异或

啥叫异或呢？男性和女性能生出孩子，否则就不行。形象吼。

0^0=0 0^1=1 1^0=1 1^1=0

简言之，相同的两个数，异或是0；不同是1

而且a⊕b⊕a=b

因此让下标和数组元素异或，再把结果异或进总长度。除了目标外都会变成0了

总之可以做到，且速度贼快

func missingNumber(nums []int) int {
    miss := len(nums)
    for i := 0; i < len(nums); i++ {
        miss ^= i ^ nums[i]
    }
    return miss
}

Runtime: 16 ms, faster than 91.23% of Go online submissions for Missing Number.

Memory Usage: 5.9 MB, less than 100.00% of Go online submissions for Missing Number.

var missingNumber = function (nums) {
  let miss = nums.length
  for (let i = 0; i < nums.length; i++) {
    miss ^= i ^ nums[i]
  }
  return miss
};

Runtime: 16 ms, faster than 91.23% of Go online submissions for Missing Number.

Memory Usage: 5.9 MB, less than 100.00% of Go online submissions for Missing Number.

更骚的是用数学

简言之，0到n全加起来，然后和数组全加起来做个减法，留下的就是缺失的

var missingNumber = function (nums) {
  const expected = nums.length * (nums.length + 1) / 2
  let sum = 0
  for (const item of nums) {
    sum += item
  }
  return expected - sum
};

Runtime: 56 ms, faster than 89.96% of JavaScript online submissions for Missing Number.

Memory Usage: 37.3 MB, less than 25.72% of JavaScript online submissions for Missing Number.

func missingNumber(nums []int) int {
    expected := len(nums) * (len(nums) + 1) / 2
    sum := 0
    for _, elem := range nums {
        sum += elem
    }
    return expected - sum
}

Runtime: 16 ms, faster than 91.23% of Go online submissions for Missing Number.

Memory Usage: 5.9 MB, less than 100.00% of Go online submissions for Missing Number.