如何在 Java 中从数字 1 到 n 的给定数组中找到缺失的数字?
java 8object oriented programmingprogramming更新于 2025/9/20 10:20:17
如果包含数字值序列的整数数组中缺少单个数字，则可以根据数字的总和或数字的异或来找到它。
基于数字的总和 −
- 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("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 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);
}
}
输出
Enter the n value: 5 Enter (n-1) numbers: 1 2 4 5 Missing number is: 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];
//对数组元素进行异或
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
