K sıralanmış massivləri birləşdirin və sıralanmış nəticəni çap edin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon GE Healthcare google microsoft
GeyimBaxılıb 511

Problem bəyanat

“Birləşdirilmiş K Sıralı Array və Çap Sıralı Çıxış” problemində k verdik seriallar müxtəlif ölçülü. Bu massivləri birləşdirmək üçün bir proqram yazın və son sıralanmış massivi nəticə olaraq yazdırın.

Giriş Formatı

Bir n tam ədədi olan ilk sətir.

Tamam x, sonra x boşluq ayrılmış tam ədədlər olan n sətir.

Çıxış formatı

Bütün massivləri birləşdirərək yaranan son massivi ehtiva edən ilk və yalnız bir sətir.

Məhdudiyyətlər

  • 1 <= n <= 10 ^ 5
  • Bütün massivlərin cəmi 10 ^ 5-dən az olacaqdır
  • 1 <= s [i] <= 10 ^ 9

misal

3
3 1 2 3
4 3 4 5 6
2 8 9
1 2 3 3 4 5 6 8 9

Explanation: Əvvəlcə 2 massivdən başlayaraq birləşirik, sonra birləşdikdən sonra 1, 2, 3, 3, 4, 5, 6 alınır. İndi 3-cü massivi bu massivə birləşdiririk. Beləliklə, son yenilənmiş massivimiz 1, 2, 3, 3, 4, 5, 6, 8, 9-dur.

Alqoritm

Optimal bir həll hər addımda cüt cütlər götürmək olacaq. Sonra iki sıralanmış massivin birləşməsinin iki göstərici texnikasından istifadə edərək cütləri birləşdirin. Beləliklə, bütün cütləri birləşdirdikdən sonra massivlərin sayı yarıya enəcəkdir. Qalan massivlərin sayı 1-ə çevrilməyənə qədər bunu davam etdirəcəyik. Beləliklə, tələb olunan addımların sayı sifariş jurnalından (k) olacaq və hər addımda O (S) vaxtını aldığımız üçün birləşmə əməliyyatları, bu yanaşmanın ümumi zaman mürəkkəbliyi olur O (S * log (k)).

1. “Bütün massivlərin ölçüsünün cəmi” ölçülü bir çıxış massivi yaradın.

2. K ölçüsündə bir min yığın yaradın və bütün massivlərdə ilk elementi min yığına daxil edin.

3. Count = 0 və n * k-dən az saya başlayın.

  1. Minimum elementi yığından (yəni kökdən) alın və çıxış massivində saxlayın, yəni çıxış [say]
  2. Yığın kökünü elementin çıxarıldığı massivdən növbəti elementlə əvəz edin. Dizinin başqa bir elementi yoxdursa, root-u sonsuz ilə əvəz edin. Kökü əvəz etdikdən sonra ağacı yığışdırın.

4. Çıxış massivini çap edin.

Həyata keçirilməsi

K Çeşidlənmiş Arrayları Birləşdirmək və Sıralanmış Çıxışı Çap etmək üçün C ++ Proqramı

#include <bits/stdc++.h> 
using namespace std; 

vector<int> mergeTwoArrays(vector<int> l, vector<int> r) 
{
  vector<int> ret; 
  int l_in = 0, r_in = 0; 
  while (l_in + r_in < l.size() + r.size()) 
  { 
    if (l_in != l.size() && (r_in == r.size() || l[l_in] < r[r_in])) 
    { 
      ret.push_back(l[l_in]); 
      l_in++; 
    } 
    else 
    { 
      ret.push_back(r[r_in]); 
      r_in++; 
    } 
  } 
  return ret; 
} 

vector<int> mergeArrays(vector<vector<int> > arr) 
{ 
  vector<vector<int> > arr_s; 
  while(arr.size() != 1) 
  { 
    arr_s.clear(); 
    for (int i = 0; i < arr.size(); i += 2) 
    { 
      if (i == arr.size() - 1) 
        arr_s.push_back(arr[i]); 
      else
        arr_s.push_back(mergeTwoArrays(arr[i],arr[i + 1])); 
    } 
    arr = arr_s; 
  } 
  return arr[0]; 
} 

int main() 
{ 
    int n;
    cin>>n;
    vector<vector<int>> v;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        vector<int> temp;
        for(int j=0;j<x;j++)
        {
            int p;
            cin>>p;
            temp.push_back(p);
        }
        v.push_back(temp);
    }
  vector<int>output = mergeArrays(v); 
  for(auto u: output)
  {
      cout<<u<<" ";
  }
  cout<<endl;
  return 0; 
} 

K S Sıralı Dizileri Birləşdirmək və Sıralanmış Çıxışı Çap etmək üçün Java Proqramı

import java.util.ArrayList;
import java.util.Scanner;
class sum
{
    public static ArrayList<Integer> mergeTwoArrays(ArrayList<Integer>  l, ArrayList<Integer>  r) 
    {
  ArrayList<Integer>  ret = new ArrayList<Integer>(); 
  int l_in = 0, r_in = 0; 
  while (l_in + r_in < l.size() + r.size()) 
  { 
    if (l_in != l.size() && (r_in == r.size() || l.get(l_in) < r.get(r_in))) 
    { 
      ret.add(l.get(l_in)); 
      l_in++; 
    } 
    else 
    { 
      ret.add(r.get(r_in)); 
      r_in++; 
    } 
  } 
  return ret; 
    }
    public static void mergeArrays(ArrayList<ArrayList<Integer> > arr)
    {
        int n = arr.size();
        ArrayList<ArrayList<Integer> >  arr_s = new ArrayList<ArrayList<Integer> >(); 
  while(arr.size() != 1) 
  { 
    arr_s.clear(); 
    for (int i = 0; i < arr.size(); i += 2) 
    { 
      if(i == arr.size() - 1) 
        arr_s.add(arr.get(i)); 
      else
        arr_s.add(mergeTwoArrays(arr.get(i), arr.get(i + 1))); 
    } 
    arr = arr_s; 
  } 
  for(int i = 0; i < arr.get(0).size(); i++) 
        { 
            System.out.print(arr.get(0).get(i) + " ");  
        }
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        ArrayList<ArrayList<Integer> > v =  new ArrayList<ArrayList<Integer> >();
        for(int i=0;i<n;i++)
        {
            int x = sr.nextInt();
            ArrayList<Integer> temp = new ArrayList<Integer>();
            for(int j=0;j<x;j++)
            {
                int p = sr.nextInt();
                temp.add(p);
            }
            v.add(temp);
        }
        mergeArrays(v);
        System.out.println();
    }
}
2
3 1 2 7
4 5 6 8 9
1 2 5 6 7 8 9

K Çeşidlənmiş Arrayları Birləşdirmək və Sortlanmış Çıxışı Çap etmək üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (s * logk) burada s bütün massivlərin ölçüsünün cəmini göstərir. Və n sıra sayını göstərir.

Kosmik Mürəkkəblik

O (lar) burada s bütün massivlərin ölçüsünün cəmini göstərir. Burada son cavabı saxlamaq üçün bu yerdən istifadə edirik.

Translate »