İki Çeşidlənmiş Dizinin Birləşdirilməsi

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance Cisco eBay Facebook Goldman Sachs google IBM LinkedIn lyft microsoft Kahin Über VMware Walmart Laboratoriyaları Arzu Yahoo Yandex
GeyimBaxılıb 243

Problem bəyanat

İki sıralanmış massivin birləşməsində birinə iki sıralanmış massiv verdik array m + n ölçülü və n ölçülü digər massivlə. N ölçülü massivi m + n ölçülü massivə birləşdirəcəyik və m + n ölçülü birləşdirilmiş massivi çap edəcəyik.

misal

Input

6 3

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

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

Buraxılış

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

Yanaşma

Burada əvvəlcə mövcud olmayan bütün elementləri böyük ölçülü massivin sonunda təyin etdik. Elementləri düzəltdikdən sonra M massivindən bir, N massivindən bir element seçib ən kiçik elementi seçib M massivindəki dəqiq vəziyyətə gətiririk. Bütün elementləri seçin və düzgün yerə qoyun. Burada bəzi hallarda ziyarət edilən bir sıra, digər elementlərdə görünməmiş qalan bəzi elementlər meydana çıxır. Sonra xoşlayırıq Bütün elementləri qurduqdan sonra ölçüsü n + m olan M massivini (böyük ölçülü massiv) çap etməliyik.

İki Sıralı Dizinin Birləşdirilməsi Alqoritmi

Diziler M [] və N [] olsun. M [] ölçüsü m + n və N [] ölçüsü n olmalıdır
1. Əvvəlcə göstəricini s olaraq təyin edin
2. M [] massivinin j-ci elementindən və N [] massivinin 0-ci elementindən başlayaraq iki massivin hər bir dəyərini müqayisə edin və elementləri M [] 'də saxlayın artan sifariş

Həyata keçirilməsi

İki Sıralı Dizini Birləşdirmək üçün C ++ Proqramı

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

İki Sıralı Dizini Birləşdirmək üçün Java Proqramı

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

İki Sıralı Dizinin Birləşdirilməsi üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi 

O (m + n), burada m və n massivlərin ölçüləridir. Burada hər iki massivi də tam bir dəfə keçirik ki, bu da bizi xətti zaman mürəkkəbliyinə aparır.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik. Buna görə yuxarıdakı məntiq bizi davamlı zaman mürəkkəbliyinə aparır.

References

Translate »