Java中找到找到从1到n的给定数组中缺失的数字
如果在包含数字值序列的整数数组中缺少单个数字，则可以基于数字总和或基于数字的异或找到它。
基于数字的总和-
n个序号的总和为[n*（n+1）]/2。使用此方法获得n个数字的和。
添加数组中的所有元素。
从n个数字的总和中减去数组中数字的总和。
示例
import java.util.Scanner;
public class MissingNumber {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("输入n值: ");
int n = sc.nextInt();
int inpuArray[] = new int[n];
System.out.println("输入(n-1)个数字: ");
for(int i=0; i<=n-2; i++) {
inpuArray[i] = sc.nextInt();
}
//寻找缺失的数字
int sumOfAll = (n*(n+1))/2;
int sumOfArray = 0;
for(int i=0; i<=n-2; i++) {
sumOfArray = sumOfArray+inpuArray[i];
}
int missingNumber = sumOfAll-sumOfArray;
System.out.println("Missing number is: "+missingNumber);
}
}输出结果
输入n值: 5 输入(n-1)个数字: 1 2 4 5 缺失的数字是: 3
使用XOR操作-查找缺失数字的另一种方法是使用XOR。
找出所有数字的XOR。
查找数组中所有数字的XOR。
然后找到两个结果的XOR。
示例
import java.util.Scanner;
public class MissingNumber {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the n value: ");
int n = sc.nextInt();
int inpuArray[] = new int[n];
System.out.println("Enter (n-1) numbers: ");
for(int i=0; i<=n-2; i++) {
inpuArray[i] = sc.nextInt();
}
//寻找丢失的数字
int xorArray = inpuArray[0];
//XOR of elements of the array
for(int i=1; i<=n-1; i++) {
xorArray = xorArray ^ i;
}
int xorAll = inpuArray[0];
//数组元素的异或运算
for(int i=1; i<=n+1; i++) {
xorAll = xorAll ^ i;
}
int missingNumber = xorArray ^ xorAll;
System.out.println("Missing number is: "+missingNumber);
}
}输出结果
Enter the n value: 5 Enter (n-1) numbers: 1 2 4 5 Missing number is: 3