By Long Luo
Leetcode 268. 丢失的数字 的题解,English version is 4 Approaches: Sorting, Hash, XOR, Math 。
方法一:暴力 + 排序
思路与算法
这是一道简单题。首先想到的方法是先进行排序,然后遍历数组,找到值不同的那个数字,如果都相同,那么结果就是 len。
代码如下所示:
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(nlogn),其中 n 是数组 nums 的长度。排序的时间复杂度是 O(nlogn),遍历数组寻找丢失的数字的时间复杂度是 O(n),因此总时间复杂度是 O(nlogn)。
- 空间复杂度:O(logn),其中 n 是数组 nums 的长度。空间复杂度主要取决于排序的递归调用栈空间。
方法二:HashSet
可以使用一个 HashSet 来记录数组中出现的数,将时间复杂度降低为 O(n)。
首先遍历数组 nums,记录数组中的每个元素,然后检查从 0 到 n 的每个整数是否在哈希集合中,不在哈希集合中的数字即为丢失的数字。由于哈希集合的每次添加元素和查找元素的时间复杂度都是 O(1),因此总时间复杂度是 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)
方法三:异或(XOR)
数组 nums 中有 n 个数,在这 n 个数的后面添加从 0 到 n 的每个整数,则添加了 n+1 个整数,共有 2n+1 个整数。
在 2n+1 个整数中,丢失的数字只在后面 n+1 个整数中出现一次,其余的数字在前面 n 个整数中(即数组中)和后面 n+1 个整数中各出现一次,即其余的数字都出现了两次。
根据出现的次数的奇偶性,可以使用按位异或运算得到丢失的数字。按位异或运算 ⊕ 满足交换律和结合律,且对任意整数 x 都满足 x⊕x=0 和 x⊕0=x。
由于上述 2n+1 个整数中,丢失的数字出现了一次,其余的数字都出现了两次,因此对上述 2n+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(1)
方法四:数学
思路与算法
从 0 到 n 的全部整数之和记为 total,根据等差数列求和公式,有:
total=i=1∑n=2n(n+1)
将数组 nums 的元素之和记为 arrSum,则 arrSum 比 total 少了丢失的一个数字,因此丢失的数字即为 total 与 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),其中 n 是数组 nums 的长度。需要 O(1) 的时间计算从 0 到 n 的全部整数之和以及需要 O(n) 的时间计算数组 nums 的元素之和。
- 空间复杂度: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. 😉😃💗