用 Java 编写一个程序，在给定的未排序整数数组中查找缺失的正数

• Z时代
• 2024-01-10
• 分类：综合

假设我们给出了一个未排序的整数数组。任务是在 [0 到 n] 范围内找到给定数组中不存在的正缺失数。例如，

输入 1 -

N = 9
arr = [0,2,5,9,1,7,4,3,6]

输出-

8

说明- 在给定的未排序数组中，'8' 是唯一缺少的正整数，因此输出为 '8'。

输入 2 -

N = 1
arr = [0]

输出-

1

说明- 在给定的数组中，“1”是唯一缺少的正整数，因此输出为“1”。

解决这个问题的方法

有几种方法可以解决这个特定问题。然而，我们可以在线性时间O(n)和常数空间 O(1) 中解决这个问题。

因为我们知道我们的数组大小为 n，并且它包含的元素正好在 [0 到 n] 范围内。因此，如果我们对每个元素及其索引与“n”进行 XOR 运算，那么我们可以找到作为数组中缺少的唯一数字的结果数字。

• 输入 N 大小的数组，元素在 [0 到 n] 范围内。

• 整数函数 findMissingNumber(int arr[], int size) 将数组及其大小作为输入并返回缺失的数字。

• 让我们将n作为缺失的数字来执行 XOR 运算。

• 迭代所有数组元素并对每个数组元素及其相对于缺失数的索引执行 XOR 运算，即n

• 现在返回丢失的数字。

示例

public class Solution {
   public static int findMissingNumber(int arr[], int size){
      int missing_no= size;
      for(int i=0;i<size;i++){
         missing_no^= i^arr[i];
      }
      return missing_no;
   }
   public static void main(String[] args){
      int arr[] = {0,4,2,1,6,3};
      int n = arr.length;
      int a=findMissingNumber(arr, n);
      System.out.println(a);
   }
}

运行上面的代码将生成输出，

5

在给定的数组 {0,4,2,1,6,3} 中，缺少 '5'，因此我们将返回 5。

以上是 用 Java 编写一个程序，在给定的未排序整数数组中查找缺失的正数 的全部内容， 来源链接： utcz.com/z/343875.html