数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究如何在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("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();
}
//Finding the missing number
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。
- 找到从1到n的所有数字的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();
}
//Finding the missing number
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];
//XOR of elements of the array
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
更新于：2019年8月2日
16K+浏览量
广告