Znajdź najmniejszą brakującą liczbę w posortowanej tablicy

Poziom trudności Łatwo
Często zadawane pytania Adobe Amazonka Apple Bloomberg Capital One Cisco eBay Facebook Goldman Sachs Google IBM JP Morgan Microsoft Nvidia wyrocznia PayPal ServiceNow Yandex
Arista Networks Szyk matematykaodwiedzajacy 591

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 zadaniu „Znajdź najmniejszą brakującą liczbę w posortowanej tablicy” daliśmy tablicę liczb całkowitych. Znajdź najmniejszą brakującą liczbę w sortowaniu o rozmiarze N. szyk posiadające unikalne elementy w zakresie od 0 do M-1, gdzie M> N.

Przykład

Wkład

[0, 1, 2, 3, 4, 6, 7, 8, 9]

Wydajność

5

Wkład

[0,1,2,4,5,6,7,8]

Wydajność

3

Wkład

[0,1,2,3,4,5,6,8,9]

Wydajność

7

Wkład

[0,1,2,3,4,5,7,8,9]

Wydajność

6

Podejście 1 do znalezienia najmniejszej brakującej liczby w posortowanej tablicy

Tutaj po prostu porównujemy indeks i element tablicy, jeśli element tablicy jest większy niż, brakuje tej liczby (i). Teraz przejdź do implementacji przy użyciu języka c ++.

Realizacja

Program w C ++

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,m;
  cin>>n>>m;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  for(int i=0;i<n;i++)
  {
      if(a[i]>i)
      {
        cout<<i<<endl;
        return 0;
      }
  }
  cout<<n<<endl;
  return 0;
}

Program Java

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int m = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int temp=0;
        for(int i=0;i<n;i++)
        {
            if(arr[i]>i)
            {
              System.out.println(i);
              temp=1;
              i=n;
            }
        }
        if(temp==0)
        System.out.println(n);
    }
}
9 11
0 1 2 3 4 5 8 9 10
6

Analiza złożoności dla znalezienia najmniejszej brakującej liczby w posortowanej tablicy

Złożoność czasowa - O (N) gdzie n reprezentuje rozmiar tablicy. Tutaj przechodzimy przez tablicę i kiedy już znajdziemy odpowiedź, drukujemy ją i zwracamy.

Złożoność przestrzeni - O (1) ponieważ nie używamy tutaj żadnej dodatkowej spacji.

Podejście 2 do znalezienia najmniejszej brakującej liczby w posortowanej tablicy

Tutaj używamy pojęcia wyszukiwania binarnego, ponieważ tablica jest już posortowana. Tutaj szukamy każdej wartości i w zakresie od 0 do M. Jeśli element nie został znaleziony, wydrukuj ten element i wróć.

Algorytm

  1. Uruchom pętlę od 0 do M-1 i zrób
  2. Wyszukaj binarnie każdy element w zakresie i sprawdź, czy liczba istnieje, czy nie.
  3. [0,1,2,4,5,6,7,8] jest podaną tablicą, więc tutaj zakres wynosi od 0 do 8. Wyszukiwanie binarne dla każdej liczby od 0 do 8 w tablicy.
  4. Najpierw wydrukuj brakujący element, będzie to najmniejszy brakujący element.

Wyjaśnienie

Tablica wejściowa:

    0 1 2 4 5

Zastosuj algorytm do tablicy wejściowej,

M = 5,

Dla i = 0,

Wyszukiwanie binarne (0, tablica wejściowa) = prawda

Dla i = 1,

Wyszukiwanie binarne (1, tablica wejściowa) = prawda

Dla i = 2,

Wyszukiwanie binarne (2, tablica wejściowa) = prawda

Dla i = 3,

Wyszukiwanie binarne (3, tablica wejściowa) = Fałsz

Dlatego najmniejszy brakujący element to = 3

Realizacja

Program w C ++

#include <bits/stdc++.h>
using namespace std;
// code for searching element is present in array or not
//using binary search
bool binary_search_missing(int arr[],int low,int high,int x)
{
  
  if(low > high)
  return false;
  
  int mid = low + (high - low)/2;
  if(arr[mid]==x)
    return true;
    
  else if(arr[mid] > x) 
    return binary_search_missing(arr,low,mid-1,x);
  else
    return binary_search_missing(arr,mid+1,high,x);
    
}
int main()
{
  
  int n,m;
  cin>>n>>m;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  for(int i=0;i<m;i++)
  {
    if(!binary_search_missing(a,0,n,i))
    {
      cout<<i;
      return 0;
    }
  }
  cout<<m;
  return 0;
}

Program Java

import java.util.Scanner;
class sum
{
    public static int binary_search_missing(int arr[],int low,int high,int x)
    {
      if(low > high)
      return 0;
      int mid = low + (high - low)/2;
      if(arr[mid]==x)
        return 1;
      else if(arr[mid] > x) 
        return binary_search_missing(arr,low,mid-1,x);
      else
        return binary_search_missing(arr,mid+1,high,x);
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int m = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int temp=0;
        for(int i=0;i<m;i++)
        {
          if(binary_search_missing(arr,0,n,i)==0)
          {
            System.out.println(i);
            temp=1;
            i=n;
          }
        }
        System.out.println(m);
    }
}
9 15
0 1 2 3 4 5 6 7 8
9

Analiza złożoności

Złożoność czasowa - O (MlogN) gdzie M to zakres elementów, a N to rozmiar tablicy. Tutaj szukamy każdej wartości i w zakresie od 0 do M, a następnie prowadzi nas to do złożoności czasowej O (mlogn).

Złożoność przestrzeni - O (1) ponieważ nie używamy tutaj żadnej dodatkowej spacji.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »