By Long Luo
Leetcode 268. 丢失的数字 ,题目如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 268. 丢失的数字 给定一个包含[0, n]中n个数的数组nums,找出[0, n]这个范围内没有出现在数组中的那个数。 示例 1: 输入:nums = [3,0,1] 输出:2 解释:n = 3,因为有 3 个数字,所以所有的数字都在范围[0,3]内。2是丢失的数字,因为它没有出现在 nums 中。 示例 2: 输入:nums = [0,1] 输出:2 解释:n = 2,因为有2个数字,所以所有的数字都在范围[0,2]内。2是丢失的数字,因为它没有出现在nums中。 示例 3: 输入:nums = [9,6,4,2,3,5,7,0,1] 输出:8 解释:n = 9,因为有9个数字,所以所有的数字都在范围[0,9] 内。8是丢失的数字,因为它没有出现在nums中。 示例 4: 输入:nums = [0] 输出:1 解释:n = 1,因为有 1 个数字,所以所有的数字都在范围[0,1]内。1是丢失的数字,因为它没有出现在 nums 中。 提示: n == nums.length 1 <= n <= 10^4 0 <= nums[i] <= n nums 中的所有数字都 独一无二 进阶:你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
方法一:暴力 + 排序
思路与算法
这是一道简单题。首先想到的方法是先进行排序 ,然后遍历数组,找到值不同的那个数字,如果都相同,那么结果就是l e n len l e n 。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 public int missingNumber (int [] nums) { int len = nums.length; Arrays.sort(nums); for (int i = 0 ; i < len; i++) { if (i != nums[i]) { return i; } } return len; }
复杂度分析:
时间复杂度:O ( n log n ) O(n \log n) O ( n log n ) ,其中n n n 是数组nums \textit{nums} nums 的长度。排序的时间复杂度是O ( n log n ) O(n \log n) O ( n log n ) ,遍历数组寻找丢失的数字的时间复杂度是O ( n ) O(n) O ( n ) ,因此总时间复杂度是O ( n log n ) O(n \log n) O ( n log n ) 。
空间复杂度:O ( log n ) O(\log n) O ( log n ) ,其中n n n 是数组nums \textit{nums} nums 的长度。空间复杂度主要取决于排序的递归调用栈空间。
方法二:HashSet
可以使用一个HashSet
来记录数组中出现的数,将时间复杂度降低为O ( n ) O(n) O ( n ) 。
首先遍历数组nums \textit{nums} nums ,记录数组中的每个元素,然后检查从0 0 0 到n n n 的每个整数是否在哈希集合中,不在哈希集合中的数字即为丢失的数字。由于哈希集合的每次添加元素和查找元素的时间复杂度都是O ( 1 ) O(1) O ( 1 ) ,因此总时间复杂度是O ( n ) O(n) O ( n ) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public static int missingNumber_set (int [] nums) { int len = nums.length; Set<Integer> set = new HashSet<>(); for (int i = 0 ; i < len; i++) { set.add(nums[i]); } for (int i = 0 ; i <= len; i++) { if (set.add(i)) { return i; } } return len; }
复杂度分析:
时间复杂度:O ( n ) O(n) O ( n )
空间复杂度:O ( n ) O(n) O ( n )
方法三:异或(XOR)
数组nums \textit{nums} nums 中有n n n 个数,在这n n n 个数的后面添加从0 0 0 到n n n 的每个整数,则添加了n + 1 n + 1 n + 1 个整数,共有2 n + 1 2n + 1 2 n + 1 个整数。
在2 n + 1 2n + 1 2 n + 1 个整数中,丢失的数字只在后面n + 1 n + 1 n + 1 个整数中出现一次,其余的数字在前面n n n 个整数中(即数组中)和后面n + 1 n + 1 n + 1 个整数中各出现一次,即其余的数字都出现了两次。
根据出现的次数的奇偶性,可以使用按位异或运算得到丢失的数字。按位异或运算⊕ \oplus ⊕ 满足交换律和结合律,且对任意整数x x x 都满足x ⊕ x = 0 x \oplus x = 0 x ⊕ x = 0 和x ⊕ 0 = x x \oplus 0 = x x ⊕ 0 = x 。
由于上述2 n + 1 2n + 1 2 n + 1 个整数中,丢失的数字出现了一次,其余的数字都出现了两次,因此对上述2 n + 1 2n + 1 2 n + 1 个整数进行按位异或运算,结果即为丢失的数字。
1 2 3 4 5 6 7 8 9 10 11 12 13 public static int missingNumber_xor (int [] nums) { int xor = 0 ; int len = nums.length; for (int i = 0 ; i < len; i++) { xor ^= nums[i]; } for (int i = 0 ; i <= len; i++) { xor ^= i; } return xor; }
复杂度分析:
时间复杂度:O ( n ) O(n) O ( n )
空间复杂度:O ( 1 ) O(1) O ( 1 )
方法四:数学公式
思路与算法
从0 0 0 到n n n 的全部整数之和记为total \textit{total} total ,根据等差数列求和公式,有:
total = ∑ i = 1 n = n ( n + 1 ) 2 \textit{total} = \sum_{i=1}^n = \dfrac{n(n+1)}{2}
total = i = 1 ∑ n = 2 n ( n + 1 )
将数组nums \textit{nums} nums 的元素之和记为arrSum \textit{arrSum} arrSum ,则arrSum \textit{arrSum} arrSum 比total \textit{total} total 少了丢失的一个数字,因此丢失的数字即为total \textit{total} total 与arrSum \textit{arrSum} arrSum 之差。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 public static int missingNumber_sum (int [] nums) { int len = nums.length; int sum = len * (len + 1 ) / 2 ; int arraySum = 0 ; for (int x : nums) { arraySum += x; } return sum - arraySum; }
复杂度分析:
时间复杂度:O ( n ) O(n) O ( n ) ,其中n n n 是数组nums \textit{nums} nums 的长度。需要O ( 1 ) O(1) O ( 1 ) 的时间计算从0 0 0 到n n n 的全部整数之和以及需要O ( n ) O(n) O ( n ) 的时间计算数组nums \textit{nums} nums 的元素之和。
空间复杂度:O ( 1 ) O(1) O ( 1 ) 。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions . 😉😃💗