如何使用java中的lamda表达式查找缺失的最小正整数

Question

that，给定一个包含N个整数的数组A，返回A中不出现的最小正整数（大于0）。

例如，给定A=[1, 3, 6, 4, 1, 2]，函数应该返回5。

给定A=[1,2,3]，函数应该返回4。

给定一个=[−1.−3] ，函数应返回1。

为以下假设编写一个有效的算法：

import java.util.*;

class Main {

   /* Utility function that puts all non-positive
   (0 and negative) numbers on left side of
   arr[] and return count of such numbers */
   static int segregate(int arr[], int size)
   {
      int j = 0, i;
      for (i = 0; i < size; i++) {
         if (arr[i] <= 0) {
            int temp;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            // increment count of non-positive
            // integers
            j++;
         }
      }

      return j;
   }

   /* Find the smallest positive missing
   number in an array that contains
   all positive integers */
   static int findMissingPositive(int arr[], int size)
   {
      int i;

      // Mark arr[i] as visited by making
      // arr[arr[i] - 1] negative. Note that
      // 1 is subtracted because index start
      // from 0 and positive numbers start from 1
      for (i = 0; i < size; i++) {
         int x = Math.abs(arr[i]);
         if (x - 1 < size && arr[x - 1] > 0)
            arr[x - 1] = -arr[x - 1];
      }

      // Return the first index value at which
      // is positive
      for (i = 0; i < size; i++)
         if (arr[i] > 0)
            return i + 1; // 1 is added becuase indexes
         // start from 0

         return size + 1;
      }

      /* Find the smallest positive missing
      number in an array that contains
      both positive and negative integers */
      static int findMissing(int arr[], int size)
      {
         // First separate positive and
         // negative numbers
         int shift = segregate(arr, size);
         int arr2[] = new int[size - shift];
         int j = 0;
         for (int i = shift; i < size; i++) {
            arr2[j] = arr[i];
            j++;
         }
         // Shift the array and call
         // findMissingPositive for
         // positive part
         return findMissingPositive(arr2, j);
      }
      // main function
      public static void main(String[] args)
      {
         int arr[] = { 0, 10, 2, -10, -20 };
         int arr_size = arr.length;
         int missing = findMissing(arr, arr_size);
         System.out.println("The smallest positive missing number is " + missing);
      }
   }
}

Answer 1

您还可以混合使用流和基本int循环：

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[] numberSet1 = {1, 3, 6, 4, 1, 2};
        int[] numberSet2 = {-1, -3};
        int[] numberSet3 = {1, 2, 3};
        System.out.println(calcularPrimero(numberSet1));
        System.out.println(calcularPrimero(numberSet2));
        System.out.println(calcularPrimero(numberSet3));
    }
    
    public static int calcularPrimero (int[] A) {
        //IntStream intStream = Arrays.stream(A).filter(x -> x >= 0).distinct().sorted();
        int[] B = Arrays.stream(A).filter(x -> x > 0).distinct().sorted().toArray();
        for (int i = 0, index = 1; i < B.length; i++, index++) {
            if (index != B[i]) {
                return index;
            }
        }
        return B.length + 1;
    }
}

Answer 2

下面您可以使用Streams查找缺少的正整数-

int ar[] = { 0, 10, 2, -10, -20 }; 
        int max = Arrays.stream(ar).max().getAsInt();
        System.err.println("maxvalue "+max);


        int val = IntStream.range(1, max).filter(i->!Arrays.stream(ar).anyMatch(x->x==i))
                .findFirst().getAsInt();

        System.out.println(val);

        int[] val1 = IntStream.range(1, max).filter(i->!Arrays.stream(ar).anyMatch(x->x==i)).map(p->p).toArray();
        System.out.println("------------------");
        IntStream.of(val1).forEach(System.out::println);

        int[] valEven = IntStream.range(1, max).filter(i->Arrays.stream(val1).anyMatch(x->i%2==0)).map(p->p).toArray();
        System.out.println("------------------");
        IntStream.of(valEven).forEach(System.out::println);     

        int[] valOdd = IntStream.range(1, max).filter(i->!Arrays.stream(val1).anyMatch(x->i%2==0)).map(p->p).toArray();

        System.out.println("------------------");
        IntStream.of(valOdd).forEach(System.out::println);      


        int[] valOdd1 = IntStream.range(1, max).filter(i->Arrays.stream(val1).noneMatch(x->i%2==0)).map(p->p).toArray();

        System.out.println("------------------");
        IntStream.of(valOdd1).forEach(System.out::println);     

        int[] valEven1 = IntStream.range(1, max).filter(i->!Arrays.stream(val1).noneMatch(x->i%2==0)).map(p->p).toArray();

        System.out.println("------------------");
        IntStream.of(valEven1).forEach(System.out::println);        

Answer 3

如果需要使用流，更直接但不是最佳的方法是创建一个无限流，从1开始，返回第一个不在arr中的流：

int[] arr = { 1, 3, 6, 4, 1, 2 };

Set<Integer> arrSet = Arrays.stream(arr).boxed().collect(Collectors.toSet());

Optional<Integer> found = IntStream.iterate(1, o -> o + 1).boxed()
        .filter(value -> !arrSet.contains(value))
        .findFirst();

found.ifPresent(System.out::println);

输出

5

正如所指出的，这是非常低效的，但就计算复杂度而言，我相信是最佳的，至少对于最坏的情况，即您必须查看所有元素的情况。