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