Java 寻找最小缺失数

最小缺失数 是指在一个元素流或数组中缺失的最小数字。该流可能包含连续或非连续的元素。如果流是连续的，那么最小缺失数就是流中的遗失数字。在本部分中，我们将讨论使用Java编程语言来寻找元素流中的遗失数字的各种方法。

数组中最小缺失数的例子

示例1

输入

arr=[1,2,3,5,6,7,8]

输出

解释 - 在上面的数组“arr”中，4和7是缺失的数字，而4是它们中最小的。所以4是最小的数字。由于序列不连续，这里没有应用缺失数字原则。

示例2

输入

: arr=[1,2,3,5,6,7,8]

结果

解释 − 在上述的数组’arr’中，缺少了4，而4是其中最小的数字。因此，4是最小的数字，并且由于序列是连续的，’4’也是给定数组中缺失的数字。

数组初始化

datatype arrayName[] = {values};
arrayName[index]=value;

示例

int array[] = {1, 2, 3, 4, 5}; //Initializing whole array
array[0]=1; //Initializing a particular value

访问数组

array[index]用于访问数组中的元素，其中index从0开始。
array[0]表示数组中的第一个元素，array[1]表示第二个元素，依此类推。

现在，我们将详细讨论如何使用Java程序查找最小的缺失数字。

方法1：使用循环语句

在这种方法中，我们首先初始化一个包含一些值的数组，然后调用一个自定义函数”missingNumber”，该函数通过迭代数组的长度返回一个在数组中缺失的值。如果数组中没有缺失的元素，则返回数组之外的第一个元素的值。

步骤

初始化一个数组。
声明一个名为missingNumber的函数（参数为arr和n）。
从0到n进行循环，并与数组中的元素进行匹配。
在循环中检查数组中是否存在所有元素。如果找到任何不在数组中的元素，则返回它。
在主方法中调用函数，并打印函数返回的值。

示例

在这个示例中，我们将使用Java提供的for循环语句来查找最小的缺失数字。

import java.util.*;
public class Main {
   public static void main(String[] args) {
      int[] arr = { 0, 1, 2, 3, 4, 5, 8,11 };
      int missing_number = missingNumber(arr, arr.length);
      System.out.println("The smallest missing number " + missing_number);
   }
   static int missingNumber(int[] arr, int n) {
      int i;
      for (i = 0; i < n; i++) {
         if (arr[i] != i) {
            return i;
         }
      }
      return i;
   }
}

输出

The smallest missing number 6

方法2：使用Java中的HashSet

在这个方法中，我们初始化一个带有一些值的数组，然后调用一个自定义函数“missingNumber”。该函数通常通过将所有元素存储在HashSet中来返回数组中缺失的值。然后我们遍历数组的长度，检查每个值是否在集合中存在，如果不存在则返回该值，如果每个元素都存在，最后我们返回n作为第一个缺失的数字。

步骤

初始化一个数组arr。
声明一个函数missingNumber(arr, n)。
声明一个HashSet，并使用add()方法将数组的所有元素添加到集合中。
循环0到n，并使用contains()方法在HashSet中查找值，如果值不存在则返回它。
在main方法中调用该函数，并打印方法返回的值。

HashSet - HashSet是一个无序的对象集合，不允许重复元素。

HashSet<datatype> objName = new HashSet<datatype>();

contains() − 这个方法检查集合中是否存在某个值，并返回一个布尔值。

setObjName.contains(value)

例子

在这个例子中，我们将使用Java中的HashSet集合以及HashSet的不同内置方法来找到最小缺失的数字。

import java.util.HashSet;
public class Main {
   public static void main(String[] args) {
      int[] arr = { 0, 1, 2, 3, 4, 5, 8,11 };
      int missing_number = missingNumber(arr, arr.length);
      System.out.println("The smallest missing number is " + missing_number);
   }
   static int missingNumber(int[] arr, int n) {
      HashSet<Integer> set = new HashSet<>();
      for (int i = 0; i < n; i++) {
         set.add(arr[i]);
      }
      for (int i = 0; i < n; i++) {
         if (!set.contains(i)) {
            return i;
         }
      }
      return n;
   }
}