0268._missing_numbers.md

Navigation

• Navigation
• Links
• Solution 1 数学方法。求出 [0..n]的和，减去数组中所有数的和。
  • range()
  • 高斯公式
• Solution 2 排序
• Solution3 哈希表(set底层是哈希表)
• Solution 4 位运算，XOR
  • 变种1
  • 变种2
  • xor总结

Links

1. https://leetcode.com/problems/missing-number/
2. https://leetcode-cn.com/problems/missing-number/

Solution 1 数学方法。求出 [0..n]的和，减去数组中所有数的和。

    时间复杂度：O(N)。sum为O(N)。
    空间复杂度：O(1)

range()

class Solution:
    def missingNumber(self, nums):
        return sum(range(len(nums)+1)) - sum(nums)

---

高斯公式

sum = n * (n + 1) / 2

class Solution:
    def missingNumber(self, nums):
        n = len(nums)

        return (n * (n + 1) / 2) - sum(nums)

---

Go

package main

func missingNumber(nums []int) int {
	n := len(nums)
	total := n * (n + 1) / 2
	nums_total := 0

	for _, num := range nums {
		nums_total += num
	}

	return total - nums_total

}

Solution 2 排序

    时间复杂度：O(NlogN)。sort为timsort
    空间复杂度：O(N)

class Solution:
    def missingNumber(self, nums):
        nums.sort()

        if nums[-1] != len(nums):
            return len(nums)

        if nums[0] != 0:
            return 0

        for i in range(1, len(nums)):
            expected_num = nums[i - 1] + 1
            if nums[i] != expected_num:
                return expected_num

---

Go

func missingNumber(nums []int) int {
    sort.Ints(nums)
    for i, num := range nums {
        if num != i {
            return i
        }
    }
    return len(nums)
}

Solution3 哈希表(set底层是哈希表)

    时间复杂度：O(N)
    空间复杂度：O(N)

class Solution:
    def missingNumber(self, nums):
        nums_set = set(nums)
        n = len(nums) + 1

        for number in range(n):
            if number not in nums_set:
                return number

---

Go

func missingNumber(nums []int) int {
    has := map[int]bool{}
    for _, v := range nums {
        has[v] = true
    }
    for i := 0; i < len(nums) ; i++ {
        if !has[i] {
            return i
        }
    }

    return len(nums)
}

Solution 4 位运算，XOR

    时间复杂度：O(N)。N次异或运算。
    空间复杂度：O(1)。

变种1

1. num xor num == 0。num xor 0 == num。
2. 如果不缺失，则列表当前的下标和数字想等。

class Solution:
    def missingNumber(self, nums):
        missing = 0

        for i in range(len(nums) + 1):
            missing ^= i

        for num in nums:
            missing ^= num

        return missing

---

变种2

由于 sum([0..n]) 恰好是这个数组的下标加上 n(列表的长度)，因此可以用一次循环完成所有的异或运算。

class Solution:
    def missingNumber(self, nums):
        missing = len(nums)
        for i, num in enumerate(nums):
            missing ^= i ^ num  # 这样做是因为xor不管顺序，例如4 ^ 6 ^ 8 == 6 ^ 4 ^ 8。
        return missing

---

Go

package main

func missingNumber(nums []int) int {
	missing := len(nums)

	for i, num := range nums {
		missing ^= i ^ num
	}

	return missing
}

xor总结

其实两种变种都是寻找pair配对（两个想等的数），能配对的互相xor为0。异或完毕之后，没有配对的（单身狗）就是missing的数。