資料結構
網路
關係資料庫管理系統 (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+瀏覽量
廣告