Scal dwie posortowane tablice

Poziom trudności Średni
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
Szyk Dwa wskaźnikiodwiedzajacy 247

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 problemie scalania dwóch posortowanych tablic daliśmy dwie posortowane tablice wejściowe, musimy połączyć te dwie tablice tak, aby początkowe liczby po całkowitym sortowaniu były w pierwszej szyk i pozostając w drugiej tablicy.

Przykład

Wkład

A [] = {1, 3, 5, 7, 9}

B [] = {2, 4, 6, 8, 10}

Wydajność

A [] = {1, 2, 3, 4, 5}

B [] = {6, 7, 8, 9, 10}

Wyjaśnienie

Scal tablicę = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Teraz układamy je w rozmiarze podanej tablicy. Pierwszy element n w pierwszej tablicy i następne m elementów w drugiej tablicy.

Tak więc końcowe tablice będą:

A [] = {1, 2, 3, 4, 5}

B [] = {6, 7, 8, 9, 10}

Algorytm

Jeśli tablice wejściowe to A i B.

1. Uruchom pętlę przez tablicę B od ostatniego elementu. W (B []) dla wszystkich B [i]

2. Porównaj elementy zaczynające się od ostatniego z tablicy A z ostatnim elementem z B i jeśli którykolwiek element został znaleziony mniej niż ostatni element z B. last = A [i], znajdź A [j] <B [i].

  • Przenieś wszystkie elementy o jedną pozycję do przodu, obok elementu znalezionego w tablicy B.
  • A [j + 1] = A [j]
  • Zastąp następny element znalezionego elementu elementem z tablicy B.
  • A [j + 1] = B [i]
  • Zaktualizuj element w B, B [i] = last.s

3. Zastosuj funkcję do podanych tablic wejściowych i wydrukuj tablice.

Realizacja

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

#include <bits/stdc++.h>
using namespace std;
//Merge function, arrays are A[],B[] and sizes M and N respectively
void Merge(int A[], int B[], int M, int N)
{
    //for all elements in B from last
    for(int i=N-1; i>=0; i--)
        {
            int j, last = A[M-1];
            // Moving elements one position ahead.
            for(j=M-2;j >= 0 && A[j]>B[i];j--)
                {
                    A[j+1] = A[j];
                }
            //Move next element and update element in B
            if(j!=M-2 || last > B[i])
                {
                    A[j+1] = B[i];
                    B[i] = last;
                }
        }
}
//function to print the given array
int PrintArray(int array[],int N)
{
    for (int i=0; i<N; i++)
       {
           cout <<array[i]<<" ";
       }
}
//Main function: To call functions on input array
int main(void)
{
    int A[] = {1, 3, 5, 7, 9};
    int B[] = {2, 4, 6, 8, 10};
    int M = sizeof(A)/sizeof(A[0]);
    int N = sizeof(B)/sizeof(B[0]);
    cout << "Input Arrays:-";
    cout << "\nArray A: ";
    PrintArray(A,M);
    cout << "\nArray B: ";
    PrintArray(B,N);
   
   //Mergeing A, B according to the condition
    Merge(A, B, M, N);
    
    cout << "\nAfter Merge:-";
    cout << "\nArray A: ";
    PrintArray(A,M);
    cout << "\nArray B: ";
    PrintArray(B,N);
    return 0;
}
Input Arrays:-
Array A: 1 3 5 7 9 
Array B: 2 4 6 8 10 
After Merge:-
Array A: 1 2 3 4 5 
Array B: 6 7 8 9 10

Program Java do łączenia dwóch posortowanych tablic

import static java.lang.Math.pow;
import java.util.Scanner;
class sum
{
    //Merge function, arrays are A[],B[] and sizes M and N respectively
    public static void Merge(int A[], int B[], int M, int N)
    {
        //for all elements in B from last
        for(int i=N-1; i>=0; i--)
            {
                int j, last = A[M-1];
                // Moving elements one position ahead.
                for(j=M-2;j >= 0 && A[j]>B[i];j--)
                    {
                        A[j+1] = A[j];
                    }
                //Move next element and update element in B
                if(j!=M-2 || last > B[i])
                    {
                        A[j+1] = B[i];
                        B[i] = last;
                    }
            }
    }
    //function to print the given array
    public static void PrintArray(int array[],int N)
    {
        for (int i=0; i<N; i++)
           {
               System.out.print(array[i]+" ");
           }
    }
    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];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int b[] = new int[n];
        for(int i=0;i<n;i++)
        {
            b[i] = sr.nextInt();
        }
        //Mergeing A, B according to the condition
        Merge(a, b, n, m);
        System.out.println("\nAfter Merge:-");
        System.out.print("\nArray A: ");
        PrintArray(a,n);
        System.out.print("\nArray B: ");
        PrintArray(b,m);
        System.out.println();
    }
}
5 5
1 3 5 7 9
2 4 6 8 10
After Merge:-

Array A: 1 2 3 4 5 
Array B: 6 7 8 9 10

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

Złożoność czasowa

O (n + m) gdzie n jest rozmiarem pierwszej tablicy, am jest rozmiarem drugiej tablicy. Tutaj po prostu przechodzimy przez wszystkie elementy obu tablicy, dlatego ta logika prowadzi nas do złożoności czasowej O (n + m).

Złożoność przestrzeni

O (1) ponieważ tutaj nie używamy żadnej dodatkowej spacji. Po prostu zamienia wartości z jednej pozycji na drugą.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »