Łączenie dwóch posortowanych tablic

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

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