Kth найбуйнейшы элемент у масіве Leetcode Solutions


Узровень складанасці серада
Часта пытаюцца ў Саман амазонка яблык ByteDance eBay Expedia facebook Google LinkedIn Microsoft Аракул Salesforce Spotify Лабараторыі Walmart
масіў Падзялі і перамагай адвал

У гэтай задачы мы павінны вярнуць k-ы па велічыні элемент у несартавана масіў. Звярніце ўвагу, што масіў можа мець дублікаты. Такім чынам, мы павінны знайсці Kth найбольшы элемент у адсартаваным парадку, а не асобны Kth найбуйнейшы элемент.

Прыклад

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

Падыход (сартавальны масіў)

Такі падыход прамалінейны. Сартаваць увесь масіў. І зараз вы можаце вызначыць любы найбуйнейшы элемент у масіве. Але нам дастаткова, каб проста знайсці Kth найбуйнейшы элемент. Менавіта таму мы можам прыйсці да лепшага падыходу.

Алгарытм

  1. Сартаваць масіў
  2. Доступ да найбуйнейшага элемента Kth з задняй часткі масіва
  3. Раздрукуйце адказ

Рэалізацыя алгарытму пошуку Kth найбуйнейшага элемента ў несартаваным масіве

Праграма 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 найбуйнейшага элемента ў несартаваным масіве

Складанасць часу

O (NlogN), бо нам трэба адсартаваць масіў. N = Памер масіва

Касмічная складанасць

O (1), паколькі мы выкарыстоўваем пастаянную прастору. Нататка: сартаваць () функцыя можа выкарыстоўваць O (N) памяць. Але гэта не заўсёды так.

Падыход (хуткі выбар)

Як мы абмяркоўвалі ў сваім папярэднім падыходзе, нам проста трэба знайсці kth самы вялікі элемент у масіве. Больш простым спосабам нам патрэбны (n - k + 1) самы маленькі элемент у масіве. Кажучы пра сартаванне, мы можам падумаць шпаркасць, які мае падобны падыход. У хуткім сартаванні, пры выбары стрыжань, мы гарантуем, што ён атрымае правільны індэкс у масіве пасля раздзела.

Што рабіць, калі мы рабілі аналагічны раздзел да (п - к) ы індэкс атрымлівае правільнае значэнне. Вось што мы будзем рабіць у гэтым падыходзе:

Kth найбуйнейшы элемент у несартаваным масіве Leetcode Solutions

Выберыце выпадковы шарнір і падзеліце масіў вакол яго. Калі ён даходзіць да індэкса, якога мы жадаем (n - k). Тады, гэта K-ы па велічыні элемент. У адваротным выпадку мы ведаем, што неабходны індэкс ляжыць альбо злева ад яго, альбо справа ад яго. Затым мы можам патэлефанаваць у раздзел () функцыя ў адпаведным падмасіў знайсці патрэбны індэкс і, такім чынам, яго значэнне.

Але, ці вышэйапісаны падыход, безумоўна, лепшы, чым сартаванне адзін? Мы ведаем, што найгоршы выпадак хуткай сартавання ўзнікае, калі мы выбіраем найменшы / найвялікшы элемент як сваю аснову, як у гэтым выпадку,

T (N) = T (N - 1) + O (1)

і падзадача амаль такая ж, як праблема, выклікаючы складанасць часу O (N * N). Падобным чынам наша функцыя падзелу можа рабіць такія выклікі. Для таго, каб вырашыць гэтую праблему, мы забяспечым, каб мы абралі выпадковы паварот у кожнай кропцы падзелу.

Алгарытм

  1. Стварыць quickSelect () функцыя, якая вяртае (N - K) -ы "найменшую”Элемент
  2. Стварыць раздзел () дапаможная функцыя, якая верне правільны індэкс любога выпадкова абраны стрыжань
  3. Цяпер, пакуль не дойдзем да кропкі, дзе раздзел () вяртае індэкс, роўны 'K«:
    • выклікаць раздзел () на a выпадковы стрыжань
    • Калі зваротны індэкс вяртаецца, тое ж самае, што і K
      • вярнуць асноўны элемент
    • У іншым выпадку, калі зваротны індэкс менш, чым K
      • выклікаць раздзел () на права падмасіў зводнага індэкса
    • У іншым выпадку, калі зваротны індэкс вяртаецца больш за K
      • выклікаць раздзел () на левая падмасіў зводнага індэкса
  4. Цяпер, калі quickSelect () вярнуў (N - K) -ы індэкс, надрукуйце вынік

Рэалізацыя алгарытму пошуку Kth найбуйнейшага элемента ў несартаваным масіве

Праграма 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 найбуйнейшага элемента ў несартаваным масіве

Складанасць часу

Суадносіны рэцыдываў можна выказаць як (N = памер масіва):

T (N) = T (N / 2) + O (N - 1)

Паколькі мы чакаем, што выпадкова абраны шарнір падзяліў масіў на дзве паловы. На яго аснове складанасць можна прыблізна ацаніць як T (N) = 2N - logN = ~ O (N).

Такім чынам, алгарытм лінейны. Аднак у горшым выпадку, калі выбраныя выпадковыя кропкі з'яўляюцца найбольшымі / найменшымі ў масіве, складанасць часу становіцца O (N * N). Але ў маштабным масіве гэта вельмі менш верагодна.

Касмічная складанасць

O (1), бо выкарыстоўваецца толькі пастаянная прастора.