Array Leetcode Solutions ရှိ Kth အကြီးဆုံးဒြပ်စင်ဖြစ်သည်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Adobe က အမေဇုံ Apple ByteDance ကို eBay Expedia Facebook က Google LinkedIn တို့ Microsoft က Oracle က Salesforce Spotify Walmart ဓာတ်ခွဲခန်းများ
အခင်းအကျင်း သွေးခွဲနှင့်အောင်နိုင် အမှိုက်ပုံ

ဒီပြproblemနာမှာ kth အကြီးဆုံး element ကို return ပြန်ရတယ် မလုံလောက်ဘူး အခင်းအကျင်း။ ဒီ array ထဲမှာပုံတူပွားနိုင်ပါတယ်။ ဒီတော့ငါတို့ရှာရမယ် Kth ကွဲပြားခြားနားသော Kth အကြီးဆုံးဒြပ်စင်မဟုတ်ဘဲစီတန်းနိုင်ရန်အတွက်အကြီးဆုံးဒြပ်စင်။

နမူနာ

A = {4 , 2 , 5 , 3 , 1}
K = 2
4
A = {7 , 2 , 6 , 4 , 3 , 5}
K = 4
4

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

ဤသည်ချဉ်းကပ်မှုဖြောင့် - ရှေ့ဆက်ဖြစ်ပါတယ်။ ခင်းကျင်းမှုတစ်ခုလုံးကိုစီပါ။ ပြီးတော့မင်းက array ထဲမှာအကြီးဆုံးဘယ်ဟာကိုမဆိုပြောပြနိုင်ပြီ။ ဒါပေမယ့်အဲဒါကိုရှာရုံနဲ့လုံလောက်ပါတယ် Kth အကြီးဆုံးဒြပ်စင်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်ပိုမိုကောင်းမွန်သောချဉ်းကပ်မှုတစ်ခုကိုပြုလုပ်နိုင်သည်။

algorithm

  1. ခင်းကျင်းမှုကိုစီပါ
  2. array ၏နောက်ကျောမှ Kth အကြီးဆုံး element ကိုရယူပါ
  3. အဖြေကိုပုံနှိပ်ပါ

Unthorted array ထဲမှာ Kth အကြီးဆုံး element ကိုရှာရန် algorithm ကိုအကောင်အထည်ဖော်ခြင်း

C ++ အစီအစဉ်

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



int KthLargest(vector <int> &a , int &k)
{
    int n = a.size();
    //kth largest = element on (n - k) index
    sort(a.begin() , a.end());
    return a[n - k];
}

int main()
{
    vector <int> a = {4 , 2 , 5 , 3 , 1};
    int k = 2;
    cout << KthLargest(a , k) << '\n';
}

Java အစီအစဉ်

import java.util.Arrays;


class Kth_largest
{
    public static int KthLargest(int[] a, int k)
    {
        int n = a.length;
        Arrays.sort(a);
        return a[n - k];
    }

    public static void main(String args[])
    {
        int a[] = {4 , 2 , 5 , 3 , 1} , k = 2;
        System.out.println(KthLargest(a , k));
    }
}
4

ရှုပ်ထွေးမှုခွဲခြမ်းစိတ်ဖြာခြင်း Kth အကြီးဆုံး element ကို unsorted array တွင်ရှာဖွေခြင်း

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

အို (NlogN), ငါတို့က array sort ဖို့လိုအပ်သကဲ့သို့။ N ကို = ခင်းကျင်း၏အရွယ်အစား

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

အို (၁)၊ ကျနော်တို့စဉ်ဆက်မပြတ်အာကာသကိုသုံးပါအဖြစ်။ မှတ်စု: မျိုး () function ကိုသုံးနိုင်သည် အို (N) မှတ်ဉာဏ်။ သို့သော်ထိုသို့အမြဲတမ်းမဟုတ်ပါ။

ချဉ်းကပ်မှု (လျင်မြန်စွာရွေးချယ်ပါ)

ကျွန်ုပ်တို့ယခင်ချဉ်းကပ်မှုတွင်ဆွေးနွေးခဲ့သည့်အတိုင်းကျွန်ုပ်တို့သည်ရှာဖွေရန်လိုအပ်သည် kth အဆိုပါခင်းကျင်းအတွက်အကြီးဆုံးဒြပ်စင်။ ရိုးရိုးလေးပြောရရင် array ထဲမှာ n (n - k + 1) အသေးငယ်ဆုံး element လိုအပ်တယ်။ မျိုးအကြောင်းပြောနေတာကျနော်တို့စဉ်းစားနိုင်ပါတယ် အမြန်ဆုံးအလားတူချဉ်းကပ်မှုရှိပြီးသော။ quicksort ၌, တစ် ဦး ရွေးချယ်ရာတွင်နေစဉ် မဏ္ဍိုင်၎င်းသည် partition ပြီးလျှင် array ၏မှန်ကန်သောအညွှန်းကိုရရှိလိမ့်မည်။

အကယ်၍ ကျွန်ုပ်တို့သည် (သို့) (သို့) ထပ်တူအခန်းကန့်ကိုခွဲထုတ်လိုက်သည်ဆိုလျှင်၊n - k) ကြိမ်မြောက်အညွှန်းကိန်းက၎င်း၏မှန်ကန်သောတန်ဖိုးကိုရရှိသွားတဲ့။ ဒါကဒီချဉ်းကပ်မှုမှာငါတို့လုပ်မယ့်အရာဖြစ်တယ်။

Leetcode Solutions သည်အမျိုးအစားခွဲခြားမထားသော Kth အကြီးဆုံးဒြပ်စင်ဖြစ်သည်

ကျပန်းမဏ္ivိုင်အချို့ကိုရွေးချယ်ပြီး၎င်းကိုဝန်းရံထားသည့်ခင်းကျင်းခြင်းကိုပိုင်းခြားပါ။ အကယ်၍ ၎င်းသည်အညွှန်းကိန်းသို့ရောက်လျှင် (n - k) ။ ဒီဟာကအကြီးဆုံး K element ပါ။ ဒီလိုမှမဟုတ်ရင်ကျနော်တို့လိုအပ်သောအညွှန်းကိန်း၏ဘယ်ဘက်သို့မဟုတ်ညာဘက်မှတည်ရှိသည်ကိုငါတို့သိကြ၏။ ကျနော်တို့ထို့နောက်ခေါ်နိုင်ပါတယ် အခန်းကန့် () သက်ဆိုင်ရာအတွက် function ကို subarray လိုအပ်သောအညွှန်းကိန်း, ထို့ကြောင့်၎င်း၏တန်ဖိုးကိုရှာရန်။

သို့သော်အထက်ပါချဉ်းကပ်နည်းသည်အမှန်ပင်ပိုမိုကောင်းမွန်သည် sorting တစ်ခုလား ကျွန်ုပ်တို့သည်အသေးငယ်ဆုံး / အကြီးမြတ်ဆုံးဒြပ်စင်ကိုထိုအဖြစ်အပျက်၌ရှိသကဲ့သို့ကျွန်ုပ်တို့၏မဏ္asိုင်အဖြစ်ရွေးချယ်လိုက်သောအခါအဆိုးရွားဆုံးသောအမြန်ပို့မှုဖြစ်ပေါ်သည်ကိုငါတို့သိသည်။

T (N) = T (N-1) + အို (1)

နှင့် subproblem O (N * N) အချိန်ရှုပ်ထွေးစေ, ပြproblemနာနီးပါးအတူတူပင်ဖြစ်ပါသည်။ အလားတူစွာကျွန်ုပ်တို့၏ partition function သည်ထိုကဲ့သို့သောဖုန်းခေါ်ဆိုခြင်းကိုပြုလုပ်နိုင်သည်။ ဤအရာကိုဖြေရှင်းရန်ကျွန်ုပ်တို့သည်ရွေးရန်သေချာစေမည် အမှတ်မဲ့ဖြစ်သော partitioning အမှုအမျိုးမျိုးရှိသမျှအမှတ်မှာမဏ္ivိုင်။

algorithm

  1. တစ်ဦး Create quickSelect () th (N - K) ကြိမ်မြောက်ပြန်လည်ရောက်ရှိသော function ကိုအသေးငယ်ဆုံး"ဒြပ်စင်
  2. တစ်ဦး Create အခန်းကန့် () မည်သည့်၏မှန်ကန်သောအညွှန်းကိန်းပြန်လာလိမ့်မည်သည့်အကူအညီ function ကို ကျပန်း ရွေးချယ်ထားမဏ္ိုင်
  3. အခုငါတို့ဘယ်မှာအမှတ်ရောက်ရှိမှီတိုင်အောင် အခန်းကန့် () 'ညီမျှတဲ့အညွှန်းကိုပြန်ပေးတယ်။K':
    • တစ် ဦး အပေါ် partition ကို () ခေါ်ပါ အမှတ်မဲ့ဖြစ်သော မဏ္ဍိုင်
    • ပြန်လာသောမဏ္indexိုင်အညွှန်းကိန်းကဲ့သို့တူညီသောလျှင် K
      • မဏ္elementိုင်ဒြပ်စင်ပြန်သွားပါ
    • အခြားပါရှိလျှင်မဏ္pိုင်အညွှန်းကိန်းပြန်ရောက်လျှင်နည်းသည် K
      • အပေါ် partition ကို () ခေါ်ပါ မှန်သော subarray မဏ္pိုင်အညွှန်းကိန်း၏
    • အခြားပါရဂူအညွှန်းကိန်းပြန်လာသောထက်ပို။ ပါက K
      • အပေါ် partition ကို () ခေါ်ပါ လက်ဝဲ subarray မဏ္pိုင်အညွှန်းကိန်း၏
  4. အခုက quickSelect () (N - K) ကြိမ်မြောက်အညွှန်းကိန်းပြန်လာရလဒ်ပုံနှိပ်ခဲ့သည်

Unthorted array ထဲမှာ Kth အကြီးဆုံး element ကိုရှာရန် algorithm ကိုအကောင်အထည်ဖော်ခြင်း

C ++ အစီအစဉ်

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



int partition(int &l , int &r , vector <int> &a)
{
    int rnd = (rand() % (r - l + 1)) + l;
    swap(a[rnd] , a[r]);

    int idx = l;
    for(int i = l ; i < r ; i++)
    {
        if(a[i] < a[r])
        {
            swap(a[i] , a[idx]);
            idx++;
        }
    }

    swap(a[idx] , a[r]);
    return idx;
}

int quickSelect(int l , int r , int k , vector <int> &a)
{
    while(l <= r)
    {
        int pivotIdx = partition(l , r , a);
        if(pivotIdx == k)
            return a[pivotIdx];
        if(pivotIdx < k)
            l = pivotIdx + 1;
        else
            r = pivotIdx - 1;
    }
    return -1;
}


int KthLargest(vector <int> &a , int &k)
{
    int n = a.size();
    //kth largest = element on (n - k) index
    return quickSelect(0 , n - 1 , n - k , a);
}

int main()
{
    vector <int> a = {4 , 2 , 5 , 3 , 1};
    int k = 2;
    cout << KthLargest(a , k) << '\n';
}

Java အစီအစဉ်

import java.util.Random;


class Kth_largest
{
    static void swap(int x , int y , int [] a)
    {
        int temp = a[y];
        a[y] = a[x];
        a[x] = temp;
        return;
    }

    static int partition(int l , int r , int [] a)
    {
        Random rndObject = new Random();
        int rnd = rndObject.nextInt(r - l + 1) + l , idx = l;
        swap(rnd , r , a);
        for(int i = l ; i < r ; i++)
        {
            if(a[i] < a[r])
            {
                swap(i , idx , a);
                idx++;
            }
        }
        swap(idx , r , a);
        return idx;
    }


    static int quickSelect(int l , int r , int k , int [] a)
    {
        while(l <= r)
        {
            int pivotIdx = partition(l , r , a);
            if(pivotIdx == k)
                return a[pivotIdx];
            if(pivotIdx < k)
                l = pivotIdx + 1;
            else
                r = pivotIdx - 1;
        }
        return -1;
    }

    public static int KthLargest(int[] a, int k)
    {
        int n = a.length;
        return quickSelect(0 , n - 1 , n - k , a);
    }


    public static void main(String args[])
    {
        int a[] = {4 , 2 , 5 , 3 , 1} , k = 2;
        System.out.println(KthLargest(a , k));
    }
}
4

ရှုပ်ထွေးမှုခွဲခြမ်းစိတ်ဖြာခြင်း Kth အကြီးဆုံး element ကို unsorted array တွင်ရှာဖွေခြင်း

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

အဆိုပါထပ်မဖြစ်အောင်စပ်လျဉ်းအဖြစ်ဖော်ပြနိုင်ပါသည် (N ကို = ခင်းကျင်း၏အရွယ်အစား):

T (N) = T (N / 2) + အို (N-1)

ကျပန်းရွေးချယ်ထားသောမဏ္ivိုင်သည်ခင်းကျင်းမှုကိုနှစ်ပိုင်းခွဲလိုက်သည်။ ၎င်းကို အခြေခံ၍ ရှုပ်ထွေးမှုကိုခန့်မှန်းတွက်ချက်နိုင်သည် T က (N) = 2N - logN = ~ အို (N) ။

ဒီတော့ algorithm ကို linear ဖြစ်ပါတယ်။ သို့သော်အဆိုးဆုံးအနေဖြင့်၊ ရွေးချယ်ထားသောကျပန်းမဏ္otsိုင်များသည်ခင်းကျင်းမှုတွင်အကြီးဆုံး / အသေးငယ်ဆုံးဖြစ်သည့်အခါအချိန်ရှုပ်ထွေးမှုဖြစ်လာသည် အို (N * N) ။ သို့သော်ကြီးမားသောအရွယ်အစားရှိသောခင်းကျင်းမှုတစ်ခုတွင်၎င်းသည်ဖြစ်ရန်မဖြစ်နိုင်ပါ။

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

အို (၁)၊ သာစဉ်ဆက်မပြတ်အာကာသကိုအသုံးပြုသည်အဖြစ်။