Sorted Array နှစ်ခုကိုပေါင်းခြင်း  


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Adobe က အမေဇုံ Apple ဘလွန်းဘာ့ဂ် ByteDance Cisco သည် ကို eBay Facebook က Goldman Sachs Google IBM က LinkedIn တို့ lyft Microsoft က Oracle က Uber VMware က Walmart ဓာတ်ခွဲခန်းများ ဆုတောင်း Yahoo က Yandex
အခင်းအကျင်း

ပြProbleနာဖော်ပြချက်  

နှစ်ခုစီထားသော arrays ပြproblemနာကိုပေါင်းစည်းသောအခါ၊ ကျွန်ုပ်တို့မှနှစ်မျိုးစီစီစဉ်ထားသည် အခင်းအကျင်း အရွယ်အစား m + n နှင့်အရွယ်အစား size နှင့်အတူအခြားခင်းကျင်းအတူ။ ကျွန်ုပ်တို့သည် n အရွယ်ခင်းကျင်းမှုကို m + n အရွယ်ခင်းကျင်းသို့ပေါင်းစည်းပြီး m + n အရွယ်ရှိသည့်ပေါင်းစည်းခင်းကိုပုံနှိပ်မည်။

နမူနာ  

input

6 3

M က [] = {1, 7, ပျက်ကွက်, ပျက်ကွက်, 124, 132, ပျက်ကွက်, 155, 200};

N ကို [] = {2, 4, 152,};

output

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

ချဉ်းကပ်နည်း  

ဤတွင်ကျွန်ုပ်တို့သည်ကြီးမားသောအရွယ်အစားခင်းကျင်းမှု၏အဆုံးတွင်ပျက်ကွက်သောအရာအားလုံးကို ဦး စွာထားခဲ့သည်။ Element တွေကိုပြုပြင်ပြီးတဲ့နောက်မှာ M array ထဲက element တစ်ခုကိုရွေးပြီး N array ထဲက element တစ်ခုကိုရွေးပြီးအသေးငယ်ဆုံး element ကိုရွေးပြီး M array ထဲမှာအတိအကျနေရာမှာထားလိုက်ပါတယ်။ ဒြပ်စင်များအားလုံးကို Pick လုပ်ပြီးမှန်ကန်သောနေရာတွင်ထားပါ။ ဤတွင်အချို့သောကိစ္စရပ်များတစ်ခုခင်းကျင်းသွားရောက်ခဲ့ပြီးနှင့်အချို့သော element တွေကိုအခြားခင်းကျင်းထဲမှာ unvisited ကျန်ရှိနေသောပေါ်ထွန်း။ နောက်ပြီး element တွေအားလုံးကိုသတ်မှတ်ပြီးတာနဲ့ n + m အရွယ်အစားကြီးမားတဲ့ array ကို print ထုတ်ဖို့လိုတယ်။

နှစ်မျိုးခွဲထားသည့် Array များကိုပေါင်းခြင်းအတွက် Algorithm  

Array ကို M [] နှင့် N [] ဖြစ်စေ။ M ၏အရွယ်အစားသည် m + n၊ N အရွယ်အစားသည် n ဖြစ်သည်
၁။ ပထမဆုံး pointer ကိုထားပါ
၂။ M [] နှင့် array N [] ၏ 2th element မှ Jth element မှ စတင်၍ array နှစ်ခု၏တန်ဖိုးတစ်ခုစီကိုနှိုင်းယှဉ်။ element များကို M [] တွင်သိုလှောင်ပါ။ တက်နိုင်ရန်အမိန့်

လည်းကြည့်ရှုပါ
အဆိုပါစကားလုံးမှန်းဆ

အကောင်အထည်ဖော်ရေး  

Sorted Array နှစ်ခုကိုပေါင်းစည်းရန် C ++ Program

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

Sorted Arrays နှစ်ခုကိုပေါင်းခြင်းအတွက် Java Program

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

နှစ်မျိုးခွဲထားသည့် Array ကိုပေါင်းခြင်းအတွက်ရှုပ်ထွေးမှုအားခွဲခြမ်းစိတ်ဖြာခြင်း  

အချိန်ရှုပ်ထွေး 

အို (m + n), m နှင့် n သည် Array အရွယ်အစားဖြစ်သည်။ ဤတွင်ကျွန်ုပ်တို့သည် arrays နှစ်ခုလုံးကိုတစ်ကြိမ်အတိအကျဖြတ်သန်းပြီး၎င်းကကျွန်ုပ်တို့အား linear အချိန်ရှုပ်ထွေးမှုကိုဖြစ်စေသည်။

လည်းကြည့်ရှုပါ
Binary Array တစ်ခု၏ Subarrays ၏ Decimal တန်ဖိုးများအတွက်ရှာဖွေမှုများ

အာကာသရှုပ်ထွေးမှု

အို (၁) ဘာလို့လဲဆိုတော့ငါတို့ဒီမှာအရန်နေရာမရှိဘူး။ ထို့ကြောင့်အထက်ပါယုတ္တိဗေဒသည်ကျွန်ုပ်တို့အားစဉ်ဆက်မပြတ်ရှုပ်ထွေးမှုသို့ ဦး တည်စေသည်။

ကိုးကား