Brak najmniejszej liczby dodatniej w niesortowanej tablicy

Poziom trudności Ciężko
Często zadawane pytania Accolita Adobe Amazonka Apple Bloomberg ByteDance Pamięci danych eBay Facebook Zestaw faktów Goldman Sachs Google JP Morgan Microsoft Morgan Stanley wyrocznia Salesforce Samsung Snapdeal Tencent Tesla Twitch Uber Laboratoria Walmart Chcieć
Szyk Booking.comodwiedzajacy 1185

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

Brak programu Java dla najmniejszej liczby dodatniej w nieposortowanej tablicy

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

Analiza złożoności

Złożoność czasowa

Na) gdzie n jest rozmiarem podanej tablicy. Tutaj przechodzimy przez tablicę tylko raz i otrzymujemy najmniejszą dodatnią brakującą liczbę.

Złożoność przestrzeni

O (1) ponieważ tutaj używamy pewnych zmiennych do obliczenia odpowiedzi.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »