Екі сұрыпталған массивті біріктіру  


Күрделілік дәрежесі орта
Жиі кіреді Adobe Amazon алма Bloomberg ByteDance Cisco еВау Facebook Голдман Сакс Google IBM LinkedIn lyft Microsoft Oracle қиятын VMware Walmart зертханалары тілек Yahoo Яндекс
Array Екі көрсеткіш

Проблемалық мәлімдеме  

Екі сұрыпталған массивті біріктіру кезінде біз екі енгізілген сұрыпталған массивті бердік, біз осы екі массивті біріктіруіміз керек, сондықтан толық сұрыпталғаннан кейінгі бастапқы сандар біріншіде болуы керек массив және екінші массивте қалады.

мысал  

енгізу

A [] = {1, 3, 5, 7, 9}

B [] = {2, 4, 6, 8, 10}

шығыс

A [] = {1, 2, 3, 4, 5}

B [] = {6, 7, 8, 9, 10}

Түсіндіру

Массивті біріктіру = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Енді оларды берілген массивтің көлемінде орналастырамыз. Бірінші жиымдағы бірінші n элемент, екінші жиымдағы келесі m элементтер.

Сонымен, соңғы массивтер

A [] = {1, 2, 3, 4, 5}

B [] = {6, 7, 8, 9, 10}

Алгоритм  

Егер енгізу массивтері А және В болса

1. В элементі арқылы циклды соңғы элементтен іске қосыңыз. Барлығы үшін [B []] B [i]

2. А массивінің соңынан басталатын элементтерді В-дің соңғы элементімен салыстырыңыз, егер кез-келген элемент В-дің соңғы элементінен аз болса = = [A [i], A [j] <B [i] табыңыз.

  • Барлық элементтерді В массивінде орналасқан элементтің жанына бір позицияға жылжытыңыз.
  • A [j + 1] = A [j]
  • Табылған элементтің келесі элементін В массивінің элементімен ауыстырыңыз.
  • A [j + 1] = B [i]
  • B элементін жаңарту, B [i] = last.s
Сондай-ақ, қараңыз
Әр түрлі үш массивтен a + b + c = қосындысы болатын үш элементті табыңыз

3. Берілген кіріс массивтерінде функцияны қолданыңыз және жиымдарды басып шығарыңыз.

Іске асыру  

Екі сұрыпталған массивтерді біріктіруге арналған C ++ бағдарламасы

#include <bits/stdc++.h>
using namespace std;
//Merge function, arrays are A[],B[] and sizes M and N respectively
void Merge(int A[], int B[], int M, int N)
{
    //for all elements in B from last
    for(int i=N-1; i>=0; i--)
        {
            int j, last = A[M-1];
            // Moving elements one position ahead.
            for(j=M-2;j >= 0 && A[j]>B[i];j--)
                {
                    A[j+1] = A[j];
                }
            //Move next element and update element in B
            if(j!=M-2 || last > B[i])
                {
                    A[j+1] = B[i];
                    B[i] = last;
                }
        }
}
//function to print the given array
int PrintArray(int array[],int N)
{
    for (int i=0; i<N; i++)
       {
           cout <<array[i]<<" ";
       }
}
//Main function: To call functions on input array
int main(void)
{
    int A[] = {1, 3, 5, 7, 9};
    int B[] = {2, 4, 6, 8, 10};
    int M = sizeof(A)/sizeof(A[0]);
    int N = sizeof(B)/sizeof(B[0]);
    cout << "Input Arrays:-";
    cout << "\nArray A: ";
    PrintArray(A,M);
    cout << "\nArray B: ";
    PrintArray(B,N);
   
   //Mergeing A, B according to the condition
    Merge(A, B, M, N);
    
    cout << "\nAfter Merge:-";
    cout << "\nArray A: ";
    PrintArray(A,M);
    cout << "\nArray B: ";
    PrintArray(B,N);
    return 0;
}
Input Arrays:-
Array A: 1 3 5 7 9 
Array B: 2 4 6 8 10 
After Merge:-
Array A: 1 2 3 4 5 
Array B: 6 7 8 9 10

Екі сұрыпталған массивті біріктіруге арналған Java бағдарламасы

import static java.lang.Math.pow;
import java.util.Scanner;
class sum
{
    //Merge function, arrays are A[],B[] and sizes M and N respectively
    public static void Merge(int A[], int B[], int M, int N)
    {
        //for all elements in B from last
        for(int i=N-1; i>=0; i--)
            {
                int j, last = A[M-1];
                // Moving elements one position ahead.
                for(j=M-2;j >= 0 && A[j]>B[i];j--)
                    {
                        A[j+1] = A[j];
                    }
                //Move next element and update element in B
                if(j!=M-2 || last > B[i])
                    {
                        A[j+1] = B[i];
                        B[i] = last;
                    }
            }
    }
    //function to print the given array
    public static void PrintArray(int array[],int N)
    {
        for (int i=0; i<N; i++)
           {
               System.out.print(array[i]+" ");
           }
    }
    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];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int b[] = new int[n];
        for(int i=0;i<n;i++)
        {
            b[i] = sr.nextInt();
        }
        //Mergeing A, B according to the condition
        Merge(a, b, n, m);
        System.out.println("\nAfter Merge:-");
        System.out.print("\nArray A: ");
        PrintArray(a,n);
        System.out.print("\nArray B: ");
        PrintArray(b,m);
        System.out.println();
    }
}
5 5
1 3 5 7 9
2 4 6 8 10
After Merge:-

Array A: 1 2 3 4 5 
Array B: 6 7 8 9 10

Екі сұрыпталған массивті біріктірудің күрделілігін талдау  

Уақыттың күрделілігі

O (n + m) Мұндағы n - бірінші жиымның өлшемі, m - екінші жиымның өлшемі. Мұнда біз тек массивтің барлық элементтерін айналып өтеміз, сондықтан бұл логика бізді O (n + m) уақыттың күрделілігіне әкеледі.

Сондай-ақ, қараңыз
Массивті жұп индекс элементтері кішірек, тақ индекс элементтері үлкен болатындай етіп реттеңіз

Ғарыштың күрделілігі

O (1) өйткені мұнда біз қосымша кеңістікті қолданбаймыз. Тек мәндерді бір позициядан екіншісіне ауыстырады.

Әдебиеттер тізімі