[数据结构与算法]0038力扣268题---丢失的数字

力扣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 中的所有数字都 独一无二

方法一：排序后遍历

方法代码：
?

? ? public int missingNumber(int[] nums) {
? ? ? ? int n = nums.length;
? ? ? ? Arrays.sort(nums);
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? if (nums[i] != i) {
? ? ? ? ? ? ? ? return i;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return n;
? ? }

方法二：数学方法

如果不缺那个数字的话，这个数组的所有数字可以组成一个等差数列，我们只需要根据公式求和，然后再减去数组中所有的数字即可，代码如下:

方法代码：

? ? public int missingNumber(int[] nums) {
? ? ? ? int n = nums.length;
? ? ? ? int total = n * (n + 1) / 2;
? ? ? ? int sum = 0;
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? sum += nums[i];
? ? ? ? }
? ? ? ? return total - sum;
? ? }

IDEA测试验证：

public class Main {
? ? public static void main(String[] args) {
? ? ? ? int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
? ? ? ? Main solution = new Main();
? ? ? ? System.out.println(solution.missingNumber(nums));
? ? }

? ? public int missingNumber(int[] nums) {
? ? ? ? int n = nums.length;
? ? ? ? int total = n * (n + 1) / 2;
? ? ? ? int sum = 0;
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? sum += nums[i];
? ? ? ? }
? ? ? ? return total - sum;
? ? }
}

输出：8

代码也可以这样写：

? ? public int missingNumber(int[] nums) {
? ? ? ? int n = nums.length;
? ? ? ? int sum = n * (n + 1) / 2;
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? sum -= nums[i];
? ? ? ? }
? ? ? ? return sum;
? ? }

方法三：位运算（异或）

数组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个整数进行按位异或运算，结果即为丢失的数字。

方法代码：

? ? public int missingNumber(int[] nums) {
? ? ? ? int num = 0;
? ? ? ? int n = nums.length;
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? num ^= nums[i];
? ? ? ? }
? ? ? ? for (int i = 0; i <= n; i++) {
? ? ? ? ? ? num ^= i;
? ? ? ? }
? ? ? ? return num;
? ? }

IDEA测试：

public class Main {
? ? public static void main(String[] args) {
? ? ? ? int[] nums = {9,6,4,2,3,5,7,0,1};
? ? ? ? Main solution = new Main();
? ? ? ? System.out.println(solution.missingNumber(nums));
? ? }

? ? public int missingNumber(int[] nums) {
? ? ? ? int num = 0;
? ? ? ? int n = nums.length;
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? num ^= nums[i];
? ? ? ? }
? ? ? ? for (int i = 0; i <= n; i++) {
? ? ? ? ? ? num ^= i;
? ? ? ? }
? ? ? ? return num;
? ? }
}

输出：8