Как найти недостающее наименьшее положительное целое число, используя выражение lamda в java

Question

что для массива A из N целых чисел возвращает наименьшее положительное целое число (больше 0), которого нет в A.

Например, для A = [1, 3, 6, 4, 1, 2], функция должна возвращать 5.

При заданном A = [1, 2, 3] функция должна возвращать 4.

При заданном A = [−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

Если вам нужно использовать stream, то более простой, но не оптимальный способ сделать это - создать бесконечный поток, начиная с 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

Как уже отмечалось, это очень неэффективно, но с точки зрения вычислительной сложности я считаю оптимальным, по крайней мере, для наихудшего случая, т.е.элементы.

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);