වර්ග කළ අරා ලීට්කෝඩ් විසඳුම ඒකාබද්ධ කරන්න


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

“වර්ග කළ අරා ඒකාබද්ධ කරන්න” යන ගැටලුවේදී අපට දෙකක් ලබා දී ඇත අරා අවරෝහණ නොවන පිළිවෙලට වර්ග කර ඇත. පළමු අරාව සම්පුර්ණයෙන්ම පුරවා නොමැති අතර දෙවන අරාවේ සියලුම අංගයන්ට ඉඩ සැලසීමට ප්‍රමාණවත් ඉඩක් ඇත. පළමු අරාවෙහි අරා දෙකේම මූලද්‍රව්‍ය අඩංගු වන අතර ඒවා වර්ග කර ඇති අරා දෙක අපි ඒකාබද්ධ කළ යුතුය බැස නොයෑම නියෝග.

උදාහරණයක්

{1 , 2 , 3 , - , - , -}
{2 , 6 , 7}
1 2 2 3 6 7
{1 , 1 , 1 ,  - , -}
{2 , 4}
1 1 1 2 4

ප්‍රවේශය (වර්ග කිරීම)

දෙවන අරාවේ සියලුම අංග අපට පළමු එකට මාරු කළ හැකිය. අවශ්‍ය ප්‍රති .ලය ලබා ගැනීම සඳහා අපට පළමු අරාව වර්ග කළ හැකිය.

ඇල්ගොරිතම

  1. I = 0 සිට i = N සඳහා, පවරන්න
    1. a [i + m] = b [i], a = පළමු අරාව, b = දෙවන අරාව
  2. පළමු අරාව වර්ග කරන්න
  3. අවශ්‍ය ප්‍රති .ලය මුද්‍රණය කරන්න

ඒකාබද්ධ කරන ලද අරා ලීට්කෝඩ් විසඳුම ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

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

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    for(int i = 0 ; i < n ; i++)
        a[i + m] = b[i];

    sort(a.begin() , a.end());
    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

ජාවා වැඩසටහන

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        for(int i = 0 ; i < n ; i++)
            a[i + m] = b[i];
        Arrays.sort(a);
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}
1 2 2 3 6 7

ඒකාබද්ධ කරන ලද අරා ලීට්කෝඩ් විසඳුමේ සංකීර්ණතා විශ්ලේෂණය

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

ඕ (ක්ලොග්කේ), කොහෙද K = N + M.. පළමු අරාවේ N = ප්‍රමාණය, දෙවන අරාවේ M = ප්‍රමාණය. පළමු අරාව සියලු N + M මූලද්‍රව්‍ය ගබඩා කිරීමෙන් පසුව අපි වර්ග කරන විට.

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

ඕ (1) විචල්යයන් සඳහා නියත මතකය භාවිතා කරන බැවින්.

ප්‍රවේශය (කරුණු දෙකක්)

අපට භාවිතා කළ හැකිය ද්වි-දර්ශකය වර්ග කළ අරා දෙක නව අරාවකට ඒකාබද්ධ කිරීමේ තාක්ෂණය. එහෙත්, මෙම නව අරාව නිර්මාණය කිරීම සඳහා අමතර ඉඩක් වැය වේ. පළමු අරාවෙහි අරා දෙකේම සියලුම අංග රඳවා තබා ගැනීමට ප්‍රමාණවත් ඉඩක් ඇති විට අපට මෙම අතිරේක අරාව මඟ හැරීමට උත්සාහ කළ හැකිය. අපට දර්ශක දෙකක් භාවිතා කළ හැකි අතර පළමු අරාවේ පිටුපස ඇති මූලද්‍රව්‍ය ඒකාබද්ධ කිරීම ආරම්භ කළ හැකිය.

අප විසින් හිස් අවකාශයේ මූලද්‍රව්‍ය නිරතුරුවම සවි කර ඇති බැවින් මෙය “අතිරේක අරාව මතකය” පිළිබඳ ගැටළුව කපා හරිනු ඇත.

වර්ග කළ අරා ලීට්කෝඩ් විසඳුම ඒකාබද්ධ කරන්න

ඇල්ගොරිතම

  1. විචල්යයන් දෙකක් ආරම්භ කරන්න i සහ j පළමු හා දෙවන අරාවෙහි අවසාන මූලද්‍රව්‍යයේ දර්ශක පිළිවෙලින් ගබඩා කිරීම.
    • i = M - 1, j = N - 1
  2. විචල්යයක් ආරම්භ කරන්න idx, පළමු අරාවේ අවසාන දර්ශකය ගබඩා කිරීම, එනම්:
    • idx = N + M - 1
  3. දැන්, මේ දෙකෙන් එකක්වත් කරන්න i or j බිංදුව බවට පත්වේ
    • A [i]> = b [j] නම්
      • [Idx] = a [i], අඩුවීම පවරන්න i
    • එසේ නැතහොත්
      • [Idx] = b [j], අඩුවීම පවරන්න j
    • අඩුවීම idx
  4. එකක් හෝ i හෝ j ශුන්‍ය නොවේ, එයින් අදහස් වන්නේ සමහර මූලද්‍රව්‍ය තවමත් ඒකාබද්ධ වී නොමැති බවයි. ඔවුන් දැනටමත් වර්ග කර ඇති ආකාරයට, අපි ඒවා ඉදිරිපස ඇති පළමු පෙළට එකතු කරමු.
  5. අතර i ශුන්‍ය නොවේ,
    1. [Idx] = a [i] පවරන්න
    2. අඩුවීම idx සහ i
  6. අතර j ශුන්‍ය නොවේ,
    1. [Idx] = b [j] පවරන්න
    2. අඩුවීම idx සහ j
  7. දැන් පළමු අරාවෙහි අවශ්‍ය සියලුම අනුපිළිවෙලවල් ඇත.

ඒකාබද්ධ කරන ලද අරා ලීට්කෝඩ් විසඳුම ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

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

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
    int i = m - 1 , j = n - 1 , idx = m + n - 1;
    while(i >= 0 && j >= 0)
    {
        if(a[i] >= b[j])
        {
            a[idx] = a[i];
            i--;
        }
        else
        {
            a[idx] = b[j];
            j--;
        }
        idx--;
    }


    while(i >= 0)
        a[idx--] = a[i--];

    while(j >= 0)
        a[idx--] = b[j--];

    return;
}

int main()
{
    vector <int> a = {1 , 2 , 3};
    vector <int> b = {2 , 6 , 7};

    int m = 3 , n = 3;
    a.resize(m + n);
    merge(a , m , b , n);
    for(int &x : a)
        cout << x << " ";

    return 0;
}

ජාවා වැඩසටහන

import java.util.Arrays;

class merge_sorted_array
{
    static void merge(int[] a , int m , int[] b , int n)
    {
        int i = m - 1 , j = n - 1 , idx = m + n - 1;
        while(i >= 0 && j >= 0)
        {
            if(a[i] >= b[j])
            {
                a[idx] = a[i];
                i--;
            }
            else
            {
                a[idx] = b[j];
                j--;
            }
            idx--;
        }

        while(i >= 0)
            a[idx--] = a[i--];

        while(j >= 0)
            a[idx--] = b[j--];

        return;
    }

    public static void main(String args[])
    {
        int m = 3 , n = 3;

        int[] a = new int[m + n];

        a[0] = 1;
        a[1] = 2;
        a[2] = 3;

        int[] b = {2 , 6 , 7};
        merge(a , m , b , n);

        for(int i = 0 ; i < a.length ; i++)
            System.out.print(a[i] + " ");
    }
}
1 2 2 3 6 7

ඒකාබද්ධ කරන ලද අරා ලීට්කෝඩ් විසඳුමේ සංකීර්ණතා විශ්ලේෂණය

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

ඕ (එන් + එම්). N = පළමු අරාවේ ප්‍රමාණය, M = දෙවන අරාවේ ප්‍රමාණය. අපි අරා දෙකම එකවර ගමන් කරන විට.

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

ඕ (1), අපි පළමු අරාවෙහි සියලුම අංග ගබඩා කරන විට. ඉතින්, ඇල්ගොරිතම වේ ස්ථානයේ.