leetcode 268 丢失的数字(missing number)

0268 missing number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

题目大意

给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。算法应该具有线性时间复杂度。你能否仅使用额外常数空间来实现?

解题思路 1

要求找出 0, 1, 2, ..., n 中缺失的那个数。基本思想是利用异或的性质，我们都知道X^X^Y = y，这意味着用相同的数做两个异或运算会消去这个数，露出原来的数。在这个解决方案中，我对数组的索引和值都应用了异或操作。在没有缺失数字的完整数组中，索引和值应该完全对应(nums[index] = index)，所以在缺失的数组中，最后剩下的是缺失的数字。

步骤：

1. 这里我们需要构造一个 X，用数组下标就可以了。数组下标是从 [0，n-1]，数字是 [0，n]，for循环依次把数组里面的数值和数组下标进行异或。
2. 把for循环异或的结果再和 n 再异或一次，即可得到缺失的数字。

Time O(n), Space O(1)

解题思路 2

这个解决方案很容易理解。假设输入为[0,1,3,4]，数组中的数字下标为[0,1,2,3]，缺失的数字之后的数值与下标都相差1，因此每个数字对应下标的差值为[0,0,1,1]，将差值相加，用数组的长度减去它，就可以得到出现差值的缺失数。

Time O(n), Space O(1)

解题思路 3

对数组先排序，然后使用二分查找

Time O(nlogn), Space O(1)

如果数组是有序的，我更喜欢二分搜索法。否则，异或方法更好。

Go

Rust