Scal dwie posortowane tablice

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

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