力扣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
