두 개의 정렬 된 배열 병합

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

두 개의 정렬 된 배열 병합 문제에서 우리는 두 개의 정렬 된 배열을 제공했습니다. 정렬 크기가 m + n이고 다른 배열은 크기가 n입니다. n 크기의 배열을 m + n 크기의 배열로 병합하고 m + n 크기의 병합 된 배열을 인쇄합니다.

예

입력

6 3

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

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

산출

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

접근

여기서 우리는 먼저 큰 크기 배열의 끝에없는 모든 요소를 ​​설정합니다. 요소를 고정한 후 M 배열에서 하나의 요소와 N 배열에서 하나의 요소를 선택하고 가장 작은 요소를 선택하여 M 배열의 정확한 위치에 배치합니다. 모든 요소를 ​​선택하고 올바른 위치에 놓습니다. 여기에서 일부 경우는 방문한 한 배열과 다른 배열에서 방문하지 않은 일부 요소가 발생합니다. 그런 다음 모든 요소를 ​​설정하면 크기가 n + m 인 M 배열 (큰 크기 배열)을 인쇄해야합니다.

두 개의 정렬 된 배열 병합을위한 알고리즘

배열을 M [] 및 N []이라고합니다. M []의 크기는 m + n이고 N []의 크기는 n입니다.
1. 먼저 포인터를 s로 설정합니다.
2. 배열 M []의 j 번째 요소와 배열 N []의 0 번째 요소에서 시작하여 두 배열의 각 값을 비교하고 M []에있는 요소를 오름차순

실시

두 개의 정렬 된 배열 병합을위한 C ++ 프로그램

#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