වර්ග කළ අරා දෙකක් ඒකාබද්ධ කිරීම  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ByteDance සිස්කෝ ඊ බේ ෆේස්බුක් ගෝල්ඩ්මන් සැක්ස් ගූගල් IBM ආයතනය LinkedIn ලයිෆ්ට් මයික්රොසොෆ්ට් ඔරකල් Uber VMware වෝල්මාර්ට් ලැබ් ප්‍රාර්ථනා කරන්න යාහූ Yandex
අරා

ගැටළු ප්රකාශය  

වර්ග කළ අරා දෙකක් ඒකාබද්ධ කිරීමේදී අපි වර්ග කළ අරා දෙකක් ලබා දී ඇත අරාව m + n ප්‍රමාණයෙන් සහ අනෙක් අරාව n ප්‍රමාණයෙන්. අපි n ප්‍රමාණයේ අරාව m + n ප්‍රමාණයේ අරාවකට ඒකාබද්ධ කර m + n ප්‍රමාණයේ ඒකාබද්ධ කළ අරාව මුද්‍රණය කරමු.

උදාහරණයක්  

ආදාන

6 3

එම් [] = {1, 7, නොපැමිණීම, නොපැමිණීම, 124, 132, නොපැමිණීම, 155, 200};

එන් [] = {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 හි jth මූලද්‍රව්‍යයෙන් සහ N අරාවෙහි 0 වන මූලද්‍රව්‍යයෙන් ආරම්භ කර අරා දෙකේ එක් එක් අගය සංසන්දනය කර M [] හි මූලද්‍රව්‍ය ගබඩා කරන්න නඟින අනුපිළිවෙල

මෙයද බලන්න
වචනය අනුමාන කරන්න

ක්රියාත්මක කිරීම  

වර්ග කළ අරා දෙකක් ඒකාබද්ධ කිරීම සඳහා සී ++ වැඩසටහන

#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

වර්ග කළ අරා දෙකක් ඒකාබද්ධ කිරීම සඳහා සංකීර්ණ විශ්ලේෂණය  

කාල සංකීර්ණත්වය 

O (m + n), m සහ n අරා වල ප්‍රමාණයන් වේ. මෙහිදී අපි අරා දෙකම හරියටම එක වරක් ගමන් කරන අතර එමඟින් රේඛීය කාල සංකීර්ණතාවයට අපව යොමු කරයි.

මෙයද බලන්න
ද්විමය අරා වල උප අරා වල දශම අගයන් සඳහා විමසුම්

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1) අපි මෙහි කිසිදු සහායක ඉඩක් භාවිතා නොකරන නිසා. ඉහත තර්කනය නිරන්තර කාල සංකීර්ණත්වයට අපව යොමු කරන්නේ එබැවිනි.

ආශ්රිත