Kth най-големият елемент в Array Leetcode Solutions


Ниво на трудност M
Често задавани в Кирпич Амазонка ябълка ByteDance иБей Expedia Facebook Google LinkedIn Microsoft Оракул Salesforce Spotify Walmart Labs
Array Разделяй и владей купчина

В този проблем трябва да върнем 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), тъй като използваме постоянно пространство. Забележка: вид() функцията може да използва НА) памет. Но това не винаги е така.

Подход (Бърз избор)

Както обсъждахме в предишния ни подход, просто трябва да намерим kth най-големият елемент в масива. По по-прост начин се нуждаем от (n - k + 1) -ия най-малък елемент в масива. Говорейки за сортиране, можем да се сетим бърз сорт, който има подобен подход. В бърза сортировка, докато избирате a опорна точка, гарантираме, че той ще достигне правилния си индекс в масива след дяла.

Ами ако направихме подобно разделяне до (n - k) th индексът получава правилната си стойност. Ето какво ще направим при този подход:

Kth най-големият елемент в несортиран масив Leetcode Solutions

Изберете произволно завъртане и разпределете масива около него. Ако стигне до индекса, който желаем (n - k). Тогава това е K-тият по големина елемент. В противен случай знаем, че необходимият индекс се намира или отляво или отдясно. След това можем да се обадим на дял () функция в съответната подмасив за да се намери необходимия индекс и следователно неговата стойност.

Но дали горният подход със сигурност е по-добър от сортиране един? Знаем, че най-лошият случай на бърза сортировка се случва, когато изберем най-малкия / най-големия елемент като наш център, както в този случай

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

а подзадачата е почти същата като проблема, причинявайки сложност във времето O (N * N). По същия начин нашата дялова функция може да извършва такива повиквания. За да разрешим това, ще гарантираме, че сме избрали a случаен въртене във всяка точка на разделяне.

алгоритъм

  1. Създаване на quickSelect () функция, която връща (N - K) th “най-малкия”Елемент
  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), тъй като се използва само постоянно пространство.