Kth унсури калонтарин дар Array Leetcode Solutions


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Adobe Amazon себ ByteDance мехаранд Expedia Facebook Google LinkedIn Microsoft Oracle Salesforce Spotify Озмоишгоҳҳои Walmart
тартиботи ҳарбӣ Тақсим кунед ва ғолиб шавед Андозаи

Дар ин масъала, мо бояд kth-и калонтаринро дар an баргардонем номураттаб асал. Дар хотир доред, ки массив метавонад нусхабардорӣ кунад. Пас, мо бояд пайдо кунем 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 дар массиви ҷудошуда

Мураккабии вақт

О (NlogN), тавре ки мо бояд массивро ҷобаҷо кунем. N = Андозаи массив

Мураккабии фазо

О (1), чунон ки мо фазои доимиро истифода мебарем. Шарҳ: навъ () функсия метавонад истифода кунад О (Н) хотира. Аммо ин на ҳамеша чунин аст.

Равиш (Интихоби зуд)

Вақте ки мо дар муносибати қаблии худ муҳокима кардем, мо бояд танҳо пайдо кардани он kth унсури калонтарин дар массив. Бо роҳи соддатар, ба мо (n - k + 1) -и хурдтарин унсури массив лозим аст. Дар бораи навъ сӯҳбат кардан, мо метавонем дар бораи он фикр кунем киксорт, ки чунин равиш дорад. Дар quicksort, ҳангоми интихоби а масофа, мо кафолат медиҳем, ки он пас аз тақсимот ба индекси дурусташ дар массив мерасад.

Чӣ мешавад, агар мо тақсимоти монандро то (n - k) индекс арзиши дурусти худро мегирад. Ин аст он чизе, ки мо дар ин равиш анҷом хоҳем дод:

Kth унсури калон дар массиви ҷудошудаи Leetcode Solutions

Як гардиши тасодуфиро интихоб кунед ва массивро дар атрофи он тақсим кунед. Агар он ба нишондиҳандаи мо расад (n - k). Пас, ин унсури Kth бузургтарин аст. Дар акси ҳол, мо медонем, ки индекси зарурӣ ё дар тарафи чап ё дар тарафи рости он ҷойгир аст. Пас мо метавонем ҳиҷоб () дар мувофиқ кор кунед зеркашӣ барои ёфтани индекси зарурӣ ва аз ин рӯ, арзиши он.

Аммо, оё равиши боло бешубҳа беҳтар аз навъ як? Мо медонем, ки ҳолати бадтарини тезгардон вақте рух медиҳад, ки мо хурдтарин / бузургтарин унсурро ҳамчун гардиши худ интихоб кунем, дар он ҳолат,

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

ва зерпроблема тақрибан бо мушкилот монанд аст, ки боиси мураккабии вақти O (N * N) мегардад. Ба ин монанд, функсияи тақсимоти мо метавонад чунин зангҳо кунад. Бо мақсади ҳалли ин, мо кафолат медиҳем, ки як ихтиёрӣ дар ҳар нуқтаи тақсимкунӣ чарх занед.

Алгоритм

  1. Сохтани а quickSelect () функсияе, ки (N - K) th “-ро бармегардонадхурдтарин”Унсур
  2. Сохтани а ҳиҷоб () функсияи ёрирасон, ки индекси дурусти ҳама чизро бармегардонад тасодуфӣ гардиши интихобшуда
  3. Ҳоло, то он ҷое, ки расидем ҳиҷоб () индексро ба 'бармегардонадK':
    • ҳиҷобро даъват кунед () дар a ихтиёрӣ масофа
    • Агар индекси пивот баргардонида шуда бошад, ҳамон аст K
      • унсури гардишро баргардонед
    • Дигар Агар индекси гардиши гардонидашуда камтар бошад K
      • ҳиҷобро () даъват кунед рост зеркашӣ индекси гардиш
    • Дигар Агар индекси гардиши гардонида беш аз K
      • ҳиҷобро () даъват кунед subarray чап индекси гардиш
  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).

Ҳамин тавр, алгоритм хатӣ аст. Аммо, дар бадтарин ҳолат, вақте ки гардишҳои тасодуфии интихобшуда ҳама калонтарин / хурдтарин дар массив мебошанд, мураккабии вақт мегардад О (N * N). Аммо дар массиви калонҳаҷм ба амал омадани он хеле камтар аст.

Мураккабии фазо

О (1), зеро танҳо фазои доимӣ истифода мешавад.