Brak najmniejszej liczby dodatniej w niesortowanej tablicy

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

W podanym nieposortowanym szyk znaleźć najmniejszą dodatnią liczbę brakującą w nieposortowanej tablicy. Dodatnia liczba całkowita nie obejmuje 0. W razie potrzeby możemy zmodyfikować oryginalną tablicę. Tablica może zawierać liczby dodatnie i ujemne.

Przykład

a. Tablica wejściowa: [3, 4, -1, 0, -2, 2, 1, 7, -8]

Wyjście: 5.
W podanej tablicy występują 1,2,3,4, 5, XNUMX, XNUMX, ale nie ma XNUMX, czyli najmniejszej dodatniej liczby brakującej w danej tablicy.

b. Tablica wejściowa: [2, 3, 7, 8, -1, -2, 0]

Wyjście: 1.
W danej tablicy nie ma 1, czyli najmniejszej dodatniej liczby brakującej w danej tablicy.

c. Tablica wejściowa: [2, 3, 7, 8, -1, -2, 0]

Wyjście: 1.
W danej tablicy nie ma 1, czyli najmniejszej dodatniej liczby brakującej w danej tablicy.

Brak algorytmu dla najmniejszej liczby dodatniej w nieposortowanej tablicy

1. Musimy znaleźć najmniejszą brakującą liczbę dodatnią, więc nie potrzebujemy liczb ujemnych. Więc tworzymy funkcję, która przenosi wszystkie liczby dodatnie na koniec tablicy i znajdujemy brakujące liczby w tablicy dodatniej.

2. W funkcji Positive_array,

• Przechodzimy przez tablicę za pomocą dwóch wskaźników, jeśli znajdziemy liczbę ujemną, zamieniamy ją ze wskaźnikiem początkowym i przesuwamy do przodu.
• Kontynuujemy to do końca tablicy i zwracamy indeks początkowy tablicy dodatniej. Która jest początkową pozycją wskaźnika, kiedy osiągamy koniec tablicy.

3. Tworzymy funkcję FindMissingPostive, która pobiera tablicę i rozmiar tablicy oraz podaje najmniejszą brakującą liczbę.

4. W tej funkcji

• za. W tablicy wejściowej, jeśli znajdziemy dodatnią liczbę całkowitą, oznaczamy ją jako odwiedzoną, zmieniając wartość w jej indeksie na ujemną. Przykład: Jeśli dana tablica to tablica []. W tej tablicy, jeśli znajdziemy 2, tworzymy tablicę [1] = -2 i tak dalej do końca tablicy tylko wtedy, gdy tablica [i] - 1 <rozmiar i tablica [tablica [i] - 1]> 0.
• Po zmodyfikowaniu tablicy. Jeśli indeks, przy którym znajdujemy pierwszą liczbę dodatnią, to k. Wtedy k + 1 to najmniejsza brakująca liczba. Jeśli nie znaleźliśmy wtedy liczby dodatniej, rozmiar tablicy + 1 jest najmniejszą brakującą liczbą.

5. Dla podanej tablicy wejściowej najpierw stosujemy funkcję Positive_array (niech zwróci j) i stosujemy FindMissingPostive na (tablica + j).

Realizacja

Brak programu C ++ dla najmniejszej liczby dodatniej w nieposortowanej tablicy

#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
 
//function to swap addresses
void swap(int *a, int *b)
{
    int temp = *a;
    *a   = *b;
    *b   = temp;
}
//In this function we move non-postive elements to the start of the array
//return the start index of start index of postive array
int positive_array(int array[], int N)
{
    int start_index = 0, i;
    for(i = 0; i < N; i++)
    {
       if (array[i] <= 0)  
       {
           swap(&array[i], &array[start_index]);
           start_index++;  // increment count of non-positive integers
       }
    }
    return start_index;
}
//In the given array this function finds the smallest missing number
//N is size of the array
//we mark the elements by making the elements at the postion(i-1)to negitive
//after modifying the array we find index at which we find first postive(j) and j+1 is the missing number.
int FindMissingPostive(int array[], int N)
{
  for(int i = 0; i < N; i++)
  {
    if(abs(array[i]) < N+1 && array[abs(array[i]) - 1] > 0)
    {
      array[abs(array[i]) - 1] = -array[abs(array[i]) - 1];
    }
  }
  for(int k = 0; k < N; k++){
    if (array[k] > 0)
    {
      return k+1;
    }
  }
  return N+1;
}
//insted of finding the missing postive integer in whole array
//we can find in postive part of the array fast.
int FindMissing(int array[], int N)
{
   int start = positive_array(array,N);
 
   return FindMissingPostive(array+start,N-start);
}
//main function to test above functions 
int main()
{
  int N;//size of the array
  cin>>N;
  int a[N];
  for(int i=0;i<N;i++)
  {
      cin>>a[i];
  }
  cout<<"smallest positive number missing: = "<<FindMissing(a,N);
  return 0;
}

import java.util.Scanner;

class sum
{
    public static int abs(int x)
    {
        if(x<0)
        {
            return -1*x;
        }
        else
        {
            return x;
        }
    }
    //In this function we move non-postive elements to the start of the array
    //return the start index of start index of postive array
    public static int positive_array(int array[], int N)
    {
        int start_index = 0, i;
        for(i = 0; i < N; i++)
        {
           if (array[i] <= 0)  
           {
               swap(array[i], array[start_index]);
               start_index++;  // increment count of non-positive integers
           }
        }
        return start_index;
    }
    //In the given array this function finds the smallest missing number
    //N is size of the array
    //we mark the elements by making the elements at the postion(i-1)to negitive
    //after modifying the array we find index at which we find first postive(j) and j+1 is the missing number.
    public static int FindMissingPostive(int array[], int N)
    {
      for(int i = 0; i < N; i++)
      {
        if(abs(array[i]) < N+1 && array[abs(array[i]) - 1] > 0)
        {
          array[abs(array[i]) - 1] = -array[abs(array[i]) - 1];
        }
      }
      for(int k = 0; k < N; k++){
        if (array[k] > 0)
        {
          return k+1;
        }
      }
      return N+1;
    }
    //insted of finding the missing postive integer in whole array
    //we can find in postive part of the array fast.
    public static int FindMissing(int array[], int N)
    {
       int start = 0;
        for(int i = 0; i < N; i++)
        {
           if (array[i] <= 0)  
           {
               array[i]=array[i]+array[start]-(array[start]=array[i]);
               start++;  // increment count of non-positive integers
           }
        }
       int temp[] = new int[N-start];
       for(int i=0;i<N-start;i++)
       {
           temp[i]=array[i+start];
       }
       return FindMissingPostive(temp,N-start);
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        System.out.println("smallest positive number missing: = "+FindMissing(a,n));
    }
}

9
3 4 -1 0 -2 2 1 7 -8

smallest positive number missing: = 5