ခွဲထားရှိ Array Leetcode ဖြေရှင်းချက်ပေါင်းစည်း  


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Adobe က အမေဇုံ Apple ဘလွန်းဘာ့ဂ် ByteDance Cisco သည် ကို eBay Expedia Facebook က Goldman Sachs Google IBM က LinkedIn တို့ lyft Microsoft က Netflix နဲ့ Oracle က စားပှဲ Uber VMware က Yahoo က Yandex
algorithms အခင်းအကျင်း coding အင်တာဗျူး အင်တာဗျူး LeetCode LeetCodeSolutions ညွှန်ပြချက်နှစ်ခု

ပြSortနာ“ Merge Sorted Arrays” မှာကျွန်တော်တို့ကိုနှစ်ခုပေးထားတယ် Array များ Non- ဆင်းနိုင်ရန်အတွက်ခွဲထားခဲ့သည်။ ပထမခင်းကျင်းမှုမှာအပြည့်အဝမပြည့်စုံပါ၊ ဒုတိယခင်းကျင်းမှု၏ပါ ၀ င်မှုအရာများအားလုံးကိုနေရာချထားရန်နေရာအလုံအလောက်ရှိသည်။ Array နှစ်ခုစလုံးကိုပေါင်းထည့်ရမည်။ ပထမ array တွင် element များပါ ၀ င်သည် မဟုတ် - ဆင်း အမိန့်။

နမူနာ  

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

ချဉ်းကပ်မှု (Sorting)  

ဒုတိယ array ၏ element အားလုံးကိုပထမတစ်ခုသို့လွှဲပြောင်းနိုင်သည်။ ထို့နောက်ကျွန်ုပ်တို့သည်လိုအပ်သောရလဒ်ရရှိရန်ပထမဆုံးခင်းကျင်းမှုကိုခွဲထုတ်နိုင်သည်။

algorithm

  1. i = 0 to i = N အတွက်သတ်မှတ်ပါ
    1. a [i + m] = ခ [i]၊ a = ပထမခင်းခြင်း၊ ခ = ဒုတိယခင်းခြင်း
  2. ပထမဆုံးခင်းကျင်းမှုကိုစီပါ
  3. လိုအပ်သောရလဒ်ပုံနှိပ်ပါ

Merge Sorted Array ကို Leetcode Solution ၏အကောင်အထည်ဖော်မှု

C ++ အစီအစဉ်

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

Java အစီအစဉ်

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

ပေါင်းစည်းထားသည့် Array Leetcode Solution ၏ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (KlogK)အဘယ်မှာရှိသနည်း K သည် = N ကို + M က။ N = ပထမဆုံးခင်းကျင်း၏အရွယ်အစား၊ M = ဒုတိယခင်းကျင်း၏အရွယ်အစား။ N + M element များအားလုံးသိမ်းဆည်းပြီးနောက်၎င်းပထမ array ကိုကျွန်ုပ်တို့ခွဲလိုက်သည်နှင့်အမျှ။

လည်းကြည့်ရှုပါ
String Leetcode Solution လျှော့ချခြင်းတိုးမြှင့်ခြင်း

အာကာသရှုပ်ထွေးမှု

အို (၁) စဉ်ဆက်မပြတ်မှတ်ဉာဏ် variable တွေကိုများအတွက်အသုံးပြုသည်အဖြစ်။

ချဉ်းကပ်မှု (ထောက်ပြသူနှစ် ဦး)  

ကျနော်တို့ကိုသုံးနိုင်သည် ညွှန်ကိန်းနှစ်ခု array ထားသော array နှစ်ခုအား array အသစ်ထဲသို့ပေါင်းစည်းရန်နည်းလမ်း။ ဒါပေမယ့်ဒီခင်းကျင်းမှုအသစ်ကိုဖန်တီးဖို့နေရာကပိုကုန်ကျလိမ့်မယ် အထူးသဖြင့်ပထမခင်းကျင်းမှုတွင် Array နှစ်ခုလုံး၏ element အားလုံးကိုသိမ်းထားရန်နေရာအလုံအလောက်ရှိလျှင်၎င်းအပို array ကိုရှောင်ရှားရန်ကျွန်ုပ်တို့ကြိုးစားနိုင်သည်။ ကျနော်တို့ pointers နှစ်ခုသုံးနိုင်သည်နှင့်ပထမ ဦး ဆုံးခင်းကျင်း၏နောက်ကျောအတွက် element တွေကိုပေါင်းစည်းစတင်နိုင်ပါသည်။

ကျွန်ုပ်တို့သည်အချည်းနှီးသောအာကာသအတွင်းရှိအရာများကို ဆက်၍ ပြုပြင်နေခြင်းကြောင့်၎င်းသည်“ extra array memory” ၏ပြproblemနာကိုလျော့နည်းစေသည်။

ခွဲထားရှိ Array Leetcode ဖြေရှင်းချက်ပေါင်းစည်းတွယ်အပ်

algorithm

  1. နှစ်ခု variable တွေကို Initialize i နှင့် j အသီးသီးပထမ ဦး ဆုံးနှင့်ဒုတိယခင်းကျင်း၏နောက်ဆုံးဒြပ်စင်၏ညွှန်းကိန်းသိုလှောင်။
    • ဈ = M က - 1, ည = N ကို - 1
  2. တစ် ဦး variable ကို Initialize idx ပါပထမခင်းခြင်း၏နောက်ဆုံးအညွှန်းကိုသိုလှောင်ခြင်းဖြစ်သည်။
    • idx = N ကို + M - 1
  3. အခုအောက်ပါတစ်ခုခုကိုလုပ်ပါ i or j သုညဖြစ်လာသည်
    • အကယ်၍ [i]> = b [j] ဖြစ်ပါက
      • တစ် ဦး [idx] = တစ် [i], decrement assign i
    • အခြားသူ
      • တစ် ဦး [idx] = ခ [ည] decrement သတ်မှတ် j
    • ဆေးရုံ idx ပါ
  4. တစ်ခုခုကို၏ ငါသို့မဟုတ် j သုညမဟုတ်အချို့သောဒြပ်စင်များပေါင်းစည်းခံရဖို့ရှိပါတယ်ဆိုလိုတာက။ ၎င်းတို့သည်အမျိုးအစားခွဲခြားထားပြီးသောကြောင့်ကျွန်ုပ်တို့သည်၎င်းတို့ကိုရှေ့တန်းရှိပထမခင်းကျင်းမှုတွင်သာဖြည့်စွက်ထားသည်။
  5. စဉ် i သုညမဖြစ်လာဘူး
    1. [idx] = a [i] သတ်မှတ်ပါ
    2. ဆေးရုံ idx ပါ နှင့် i
  6. စဉ် j သုညမဖြစ်လာဘူး
    1. [idx] = ခ [j] သတ်မှတ်ပါ
    2. ဆေးရုံ idx ပါ နှင့် j
  7. ပထမဆုံး array တွင် element များအားလုံးလိုအပ်သောစီစဉ်ထားရှိထားပါသည်။

Merge Sorted Array ကို Leetcode Solution ၏အကောင်အထည်ဖော်မှု

C ++ အစီအစဉ်

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

Java အစီအစဉ်

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

ပေါင်းစည်းထားသည့် Array Leetcode Solution ၏ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N + M). N = ပထမ ဦး ဆုံးခင်းကျင်း၏အရွယ်အစား, M = ဒုတိယခင်းကျင်း၏အရွယ်အစား။ Array နှစ်ခုလုံးကိုဖြတ်ပြီးသွားပြီ။

လည်းကြည့်ရှုပါ
လေး Leetcode ဖြေရှင်းချက်၏ပါဝါ

အာကာသရှုပ်ထွေးမှု

အို (၁)၊ element တွေအားလုံးကိုပထမ array ထဲမှာသိမ်းထားတာပေါ့။ ဒီတော့ algorithm ကိုဖြစ်ပါတယ် နေရာ.