Łączenie dwóch posortowanych tablic

Poziom trudności Łatwo
Często zadawane pytania Adobe Amazonka Apple Bloomberg ByteDance Cisco eBay Facebook Goldman Sachs Google IBM LinkedIn lyft Microsoft wyrocznia Uber VMware Laboratoria Walmart Chcieć Yahoo Yandex
Szykodwiedzajacy 305

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

Łącząc dwie posortowane tablice, daliśmy dwie posortowane tablice, jedną szyk o rozmiarze m + n, a druga tablica o rozmiarze n. Połączymy tablicę o rozmiarze n z tablicą o rozmiarze m + n i wydrukujemy połączoną tablicę o rozmiarze m + n.

Przykład

Wkład

6 3

M [] = {1, 7, brak, brak, 124, 132, brak, 155, 200};

N [] = {2, 4, 152,};

Wydajność

{1, 2, 4, 7, 124, 132, 152, 155, 200}

Podejście

Tutaj najpierw ustawiamy wszystkie nieobecne elementy na końcu tablicy o dużym rozmiarze. Po zamocowaniu elementów wybieramy jeden element z tablicy M i jeden element z tablicy N i wybieramy najmniejszy element i umieszczamy go na dokładnej pozycji w tablicy M. Wybierz wszystkie elementy i ułóż je we właściwej pozycji. W tym miejscu pojawiają się przypadki, gdy jedna odwiedzona tablica jest odwiedzana, a niektóre elementy pozostają niewidoczne w innej tablicy. Następnie lubimy Gdy ustawimy wszystkie elementy, musimy wydrukować tablicę M (tablica o dużych rozmiarach), której rozmiar n + m.

Algorytm łączenia dwóch posortowanych tablic

Niech tablice będą M [] i N []. Rozmiar M [] oznacza m + n, a rozmiar N [] oznacza n
1. Najpierw ustaw wskaźnik na s
2. Zacznij od j-tego elementu tablicy M [] i zerowego elementu tablicy N [] i porównaj każdą wartość z dwóch tablic i zapisz elementy w M [] w rosnąco

Realizacja

Program C ++ do łączenia dwóch posortowanych tablic

#include <bits/stdc++.h>
#define absent INT_MAX
using namespace std;
int transform(int M[],int n)
{
  int j = n-1;
  for(int i=n-1;i>=0;i--)
  {
    if(M[i] != absent)
    {
      M[j]=M[i];
      j--;
    }
  }
  return (j+1); //jth index implies (j+1) elements absent
}
int main()
{
  int M[] = {1, 7, absent, absent, 124, 132, absent, 155, 200};
  int N[] = {2,4,152};
  int sizeM = sizeof(M)/sizeof(M[0]) , sizeN = sizeof(N)/sizeof(N[0]);
  
  int no_absent = transform(M,sizeM); //moves all the valid elements to the end and returns the number of elements absent  
  
  int m = no_absent , n = 0; // variables pointing at no_absent index and 0th index of M and N respectively
  int l = 0; //to fill the M[]
  
  while(n < sizeN and m < sizeM) //till any of the one array ends
  {
  
    if(M[m] <= N[n]) 
      {
        M[l++]=M[m++];  //assign the smaller and increase the index of that array
      }
    else
      M[l++]=N[n++];
  }
  
  while(m < sizeM) //if some elements have remained in M then we can directly add them
    M[l++] = M[m++];
  while(n < sizeN) //if some elements have remained in N then we can directly add them
    M[l++] = N[n++];
    
  for(int i=0;i<sizeM;i++)
    cout<<M[i]<<" ";
    
  return 0;
}

Program Java do łączenia dwóch posortowanych tablic

import java.util.Scanner;
import java.util.Stack;
class sum
{
    public static int transform(int M[],int n)
    {
      int j = n-1;
      for(int i=n-1;i>=0;i--)
      {
        if(M[i] != -1)
        {
          M[j]=M[i];
          j--;
        }
      }
      return (j+1); //jth index implies (j+1) elements absent
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int m = sr.nextInt();
        int a[] = new int[n+m+1];
        int b[] = new int[m];
        for(int i=0;i<(n+m);i++)
        {
            a[i] = sr.nextInt();
        }
        for(int i=0;i<m;i++)
        {
            b[i] = sr.nextInt();
        }
        int no_absent = transform(a,n+m); //moves all the valid elements to the end and returns the number of elements absent  
        
        int m1 = no_absent , n1 = 0; // variables pointing at no_absent index and 0th index of M and N respectively
        int l = 0; //to fill the M[]
        while((n1 < m) && (m1 < (m+n))) //till any of the one array ends
        {
          if(a[m1] <= b[n1]) 
            {
              a[l++]=a[m1++];  //assign the smaller and increase the index of that array
            }
          else
            a[l++]=b[n1++];
        }
        while(m1 < (m+n)) //if some elements have remained in M then we can directly add them
          a[l++] = a[m1++];
        while(n1 < m) //if some elements have remained in N then we can directly add them
          a[l++] = b[n1++];
        for(int i=0;i<(m+n);i++)
          System.out.print(a[i]+" ");
        System.out.println();
    }
}
6 3
1 7 -1 -1 124 132 -1 155 200
2 4 152
1 2 4 7 124 132 152 155 200

Analiza złożoności łączenia dwóch posortowanych tablic

Złożoność czasowa 

O (m + n), gdzie m i n to rozmiary tablic. Tutaj przechodzimy przez obie tablice dokładnie jeden raz, co prowadzi nas do liniowej złożoności czasowej.

Złożoność przestrzeni

O (1) ponieważ nie używamy tutaj żadnej dodatkowej spacji. Dlatego powyższa logika prowadzi nas do stałej złożoności czasowej.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »