ធាតុធំជាងគេទី ១ នៅក្នុងដំណោះស្រាយអារេឡឺកូដ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ByteDance របស់ eBay Expedia Facebook ក្រុមហ៊ុន google LinkedIn ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Oracle ការលក់ តាម Online បន្ទប់ពិសោធន៍វ៉លម៉ាត
អារេ ចែកនិងយកឈ្នះ គំនរ

នៅក្នុងបញ្ហានេះយើងត្រូវត្រឡប់ធាតុធំបំផុតទី ១ ក្នុង an មិនបានតម្រៀប អារេ។ ចំណាំថាអារេអាចមានស្ទួន។ ដូច្នេះយើងត្រូវរកឯកសារ ខេត ធាតុធំបំផុតតាមលំដាប់លំដោយមិនមែនជាធាតុធំជាងគេរបស់ខេតទេ។

តារាង​មាតិកា

ឧទាហរណ៍

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

វិធីសាស្រ្ត (តំរៀបជួរ)

វិធីសាស្រ្តនេះគឺឆ្ពោះទៅមុខត្រង់។ តម្រៀបអារេទាំងមូល។ ហើយឥឡូវនេះអ្នកអាចប្រាប់ពីធាតុធំបំផុតណាមួយនៅក្នុងអារេ។ ប៉ុន្តែវាគ្រប់គ្រាន់ហើយសម្រាប់ពួកយើងគ្រាន់តែស្វែងរកសៀវភៅ ខេត ធាតុធំបំផុត។ នោះហើយជាមូលហេតុដែលយើងអាចបង្កើតវិធីសាស្រ្តប្រសើរជាងមុន។

ក្បួនដោះស្រាយ

  1. តម្រៀបអារេ
  2. ចូលប្រើធាតុធំបំផុតខេតពីខាងក្រោយអារេ
  3. បោះពុម្ពចម្លើយ

ការអនុវត្តក្បួនដោះស្រាយដើម្បីរកឃើញធាតុធំបំផុតរបស់ខេតនៅក្នុងអារេដែលមិនបានតម្រៀប

កម្មវិធី 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';
}

កម្មវិធីចាវ៉ា

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

ការវិភាគស្មុគស្មាញនៃការរកឃើញធាតុធំបំផុតរបស់ខេតនៅក្នុងអារេដែលមិនបានតម្រៀប

ស្មុគស្មាញពេលវេលា

O (NlogN)ដូចដែលយើងត្រូវការតម្រៀបអារេ។ N = ទំហំអារេ

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), ដូចដែលយើងប្រើទំហំថេរ។ ចំណាំ: តម្រៀប () មុខងារអាចប្រើ O (N) ការចងចាំ។ ប៉ុន្តែនោះមិនតែងតែជាករណីនោះទេ។

វិធីសាស្រ្ត (ជ្រើសរើសរហ័ស)

ដូចដែលយើងបានពិភាក្សានៅក្នុងវិធីសាស្រ្តមុនរបស់យើងយើងគ្រាន់តែត្រូវការរកឯកសារ kth ធាតុធំបំផុតនៅក្នុងអារេ។ តាមវិធីសាមញ្ញយើងត្រូវការធាតុតូចបំផុត (n - k + 1) នៅក្នុងអារេ។ និយាយអំពីការតម្រៀបយើងអាចគិតបាន quicksortដែលមានវិធីសាស្រ្តស្រដៀងគ្នា។ នៅក្នុងសេនស័រខណៈពេលជ្រើសរើសយកមួយ pivotយើងធានាថាវាទទួលបានសន្ទស្សន៍ត្រឹមត្រូវរបស់វានៅក្នុងអារេបន្ទាប់ពីភាគថាស។

ចុះបើយើងចែកភាគថាសស្រដៀងគ្នារហូតដល់ (n - គ) សន្ទស្សន៍នេះទទួលបានតម្លៃត្រឹមត្រូវ។ នេះជាអ្វីដែលយើងនឹងធ្វើក្នុងវិធីសាស្រ្តនេះ៖

ធាតុធំជាងគេទី ១ នៅក្នុងអារេឡេហ្សិចសូលូសិន

ជ្រើសរើសអ្នកជំនួយការចៃដន្យខ្លះហើយចែកជួរនៅជុំវិញនោះ។ ប្រសិនបើវាទៅដល់សន្ទស្សន៍ដែលយើងចង់បាន (n - k) ។ បន្ទាប់មកនេះគឺជាធាតុធំបំផុតរបស់ខេត។ បើមិនដូច្នោះទេយើងដឹងថាសន្ទស្សន៍ដែលត្រូវការស្ថិតនៅខាងឆ្វេងរបស់វាឬនៅខាងស្តាំរបស់វា។ បន្ទាប់មកយើងអាចហៅបាន ភាគថាស () មុខងារដែលត្រូវគ្នា subarray ដើម្បីរកលិបិក្រមដែលត្រូវការហើយដូច្នេះតម្លៃរបស់វា។

ប៉ុន្តែនេះគឺជាវិធីសាស្រ្តខាងលើពិតជាប្រសើរជាង តម្រៀប មួយ? យើងដឹងហើយថាករណីរហ័សបំផុតកើតឡើងនៅពេលយើងជ្រើសរើសយកធាតុតូចបំផុត / ធំបំផុតធ្វើជាស្នូលរបស់យើង

T (N) = ធី (N - ១) + អូ (១)

ហើយធាតុរងគឺស្ទើរតែដូចគ្នានឹងបញ្ហាដែលបណ្តាលឱ្យស្មុគស្មាញពេលវេលា O (N * N) ។ ស្រដៀងគ្នានេះដែរមុខងារចែករបស់យើងអាចធ្វើការហៅបែបនេះ។ ដើម្បីដោះស្រាយបញ្ហានេះយើងនឹងធានាថាយើងជ្រើសរើសយកក ចៃដន្យ អ្នកជំនួយការនៅគ្រប់ចំណុចនៃការចែកភាគថាស។

ក្បួនដោះស្រាយ

  1. បង្កើត quickSelect () មុខងារដែលត្រឡប់ (N - K) ទី“តូចបំផុតធាតុ
  2. បង្កើត ភាគថាស () មុខងារជំនួយដែលនឹងត្រឡប់លិបិក្រមត្រឹមត្រូវ ដោយចៃដន្យ អ្នកជំនួយការដែលបានជ្រើសរើស
  3. ឥឡូវនេះរហូតដល់យើងឈានដល់ចំនុចមួយ ភាគថាស () ត្រឡប់សន្ទស្សន៍ស្មើនឹង 'K'៖
    • ហៅភាគថាស () លើក ចៃដន្យ pivot
    • ប្រសិនបើសន្ទស្សន៍អ្នកជំនួយការត្រឡប់មកវិញគឺដូចគ្នានឹង K
      • ត្រឡប់ធាតុជំនួយ
    • ផ្សេងទៀតប្រសិនបើសន្ទស្សន៍អ្នកជំនួយការត្រឡប់មកវិញគឺតិចជាង K
      • ហៅភាគថាស () បើក នៅខាងស្ដាំ subarray នៃសន្ទស្សន៍អ្នកជំនួយការទិន្នន័យ
    • បើសិនបើសន្ទស្សន៍អ្នកជំនួយការត្រឡប់មកវិញគឺច្រើនជាង K
      • ហៅភាគថាស () បើក subarray ខាងឆ្វេង នៃសន្ទស្សន៍អ្នកជំនួយការទិន្នន័យ
  4. ឥឡូវនេះថា quickSelect () បានត្រឡប់សន្ទស្សន៍ (N - K) ទីបោះពុម្ពលទ្ធផល

ការអនុវត្តក្បួនដោះស្រាយដើម្បីរកឃើញធាតុធំបំផុតរបស់ខេតនៅក្នុងអារេដែលមិនបានតម្រៀប

កម្មវិធី 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';
}

កម្មវិធីចាវ៉ា

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

ការវិភាគស្មុគស្មាញនៃការរកឃើញធាតុធំបំផុតរបស់ខេតនៅក្នុងអារេដែលមិនបានតម្រៀប

ស្មុគស្មាញពេលវេលា

ទំនាក់ទំនងកើតឡើងអាចត្រូវបានបង្ហាញជា (N = ទំហំនៃអារេ):

T (N) = T (N / ២) + O (N - ១)

ដោយសារតែយើងរំពឹងថាអ្នកជំនួយការដែលបានជ្រើសរើសដោយចៃដន្យបានបែងចែកអារេជាពីរផ្នែក។ ផ្អែកលើវាភាពស្មុគស្មាញអាចត្រូវបានប៉ាន់ស្មានប្រហែល T (N) = 2N - logN = ~ អូ (អិន) ។

ដូច្នេះក្បួនដោះស្រាយគឺលីនេអ៊ែរ។ ទោះយ៉ាងណាក៏ដោយក្នុងករណីដ៏អាក្រក់បំផុតនៅពេលដែលការជ្រើសរើសព្រួញចៃដន្យត្រូវបានជ្រើសរើសធំបំផុត / តូចជាងគេបំផុតនៅក្នុងអារេពេលវេលាស្មុគស្មាញ O (N * N) ។ ប៉ុន្តែនៅក្នុងអារេដែលមានទំហំធំវាទំនងជាមិនកើតឡើងទេ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), ដោយប្រើតែទំហំថេរប៉ុណ្ណោះ។