Kth ամենամեծ տարրը Array Leetcode Solutions- ում


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Adobe Amazon խնձոր ByteDance eBay Expedia facebook Google LinkedIn Microsoft Պատգամախոս Salesforce Spotify Walmart Labs
Դասավորություն Բաժանել եւ նվաճել Կույտ

Այս խնդրում մենք պետք է վերադարձնենք kth- ի ամենամեծ տարրը ան-ում չկարգավորված դասավորություն, Նշենք, որ զանգվածը կարող է ունենալ կրկնօրինակ: Այսպիսով, մենք պետք է գտնենք այն Կթ տեսակավորված կարգով ամենամեծ տարրը, այլ ոչ թե հստակ Kth ամենամեծ տարրը:

Օրինակ

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

Մոտեցում (զանգվածի տեսակավորում)

Այս մոտեցումն ուղիղ է: Տեսակավորել ամբողջ զանգվածը: Եվ այժմ դուք կարող եք ասել զանգվածի ցանկացած ամենամեծ տարրը: Բայց բավական է, որ մենք պարզապես գտնենք այն Կթ ամենամեծ տարրը: Այդ պատճառով մենք կարող ենք ավելի լավ մոտեցում ցուցաբերել:

Ալգորիթմ

  1. Տեսակավորել զանգվածը
  2. Accessանգվածի հետևից մուտք գործեք 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 ամենամեծ տարրը գտնելու համար

Timeամանակի բարդություն

O (NlogN), քանի որ մենք պետք է տեսակավորենք զանգվածը: N = զանգվածի չափը

Տիեզերական բարդություն

O (1), քանի որ մենք օգտագործում ենք անընդհատ տարածություն: Նշում: տեսակավորել () ֆունկցիան կարող է օգտագործել ՎՐԱ) հիշողություն Բայց դա միշտ չէ, որ գործն է:

Մոտեցում (արագ ընտրություն)

Ինչպես մենք քննարկեցինք մեր նախորդ մոտեցման մեջ, մենք պարզապես պետք է գտնենք այն kth զանգվածի ամենամեծ տարրը: Ավելի պարզ եղանակով, մեզ անհրաժեշտ է զանգվածում (n - k + 1) ամենափոքր տարրը: Խոսելով տեսակավորման մասին ՝ մենք կարող ենք մտածել quicksort, որն ունի նմանատիպ մոտեցում: Quicksort- ում, միաժամանակ ընտրելով ա առանցք, մենք ապահովում ենք, որ այն բաժանումից հետո հասնի զանգվածի իր ճիշտ ցուցանիշին:

Ինչ կլինի, եթե մենք նմանատիպ բաժանում կատարենք մինչև (n - k) րդ ինդեքսը ստանում է իր ճիշտ արժեքը: Սա այն է, ինչ մենք պատրաստվում ենք անել այս մոտեցման մեջ.

Kth ամենամեծ տարրը չհավաքված զանգված Leetcode Solutions- ում

Ընտրեք պատահական առանցք և բաժանեք զանգվածը դրա շուրջ: Եթե ​​հասնում է ցանկալի ցուցանիշին (n - k): Հետևաբար, սա ամենամեծ Kth տարրն է: Հակառակ դեպքում, մենք գիտենք, որ պահանջվող ինդեքսը գտնվում է կամ դրա ձախ կողմում, կամ դրանից աջ: Դրանից հետո մենք կարող ենք զանգահարել միջնորմ () գործառույթը համապատասխան ենթաշերտ գտնել անհրաժեշտ ցուցանիշը, և, հետևաբար, դրա արժեքը:

Բայց արդյո՞ք վերը նշված մոտեցումն ավելի լավ է, քան այն տեսակավորում մեկը? Մենք գիտենք, որ quicksort- ի ամենավատ դեպքը տեղի է ունենում, երբ որպես առանցք ընտրում ենք ամենափոքր / մեծագույն տարրը, ինչպես այդ դեպքում

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

և ենթածրագիրը գրեթե նույնն է, ինչ խնդիրը, առաջացնելով O (N * N) ժամանակի բարդություն: Նմանապես, մեր բաժանման գործառույթը կարող է կատարել այդպիսի զանգեր: Դա լուծելու համար մենք կապահովենք, որ ընտրենք ա պատահական առանցք բաժանման յուրաքանչյուր կետում:

Ալգորիթմ

  1. Ստեղծել QuickSelect () գործառույթը, որը վերադարձնում է (N - K) - րդ «ամենափոքրը" տարր
  2. Ստեղծել միջնորմ () օգնականի գործառույթ, որը կվերադարձնի ցանկացածի ճիշտ ցուցիչը պատահական ընտրված առանցք
  3. Հիմա, մինչև հասնենք այն կետին, որտեղ միջնորմ () վերադարձնում է ցուցանիշը հավասար է 'K':
    • զանգահարել միջնորմ () ա պատահական առանցք
    • Եթե ​​վերադարձված առանցքային ինդեքսը նույնն է, ինչ 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 ամենամեծ տարրը գտնելու համար

Timeամանակի բարդություն

Կրկնության հարաբերությունը կարող է արտահայտվել որպես (N = զանգվածի չափը):

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

Քանի որ մենք ակնկալում ենք, որ պատահականորեն ընտրված առանցքը զանգվածը բաժանեց երկու մասի: Դրա հիման վրա բարդությունը կարող է մոտավորապես գնահատվել որպես T (N) = 2N - logN = ~ O (N):

Այսպիսով, ալգորիթմը գծային է: Այնուամենայնիվ, վատթարագույն դեպքում, երբ ընտրված պատահական առանցքները զանգվածում ամենամեծ / ամենափոքրն են, ժամանակի բարդությունը դառնում է O (N * N) Բայց մեծ չափսի զանգվածում դա շատ ավելի քիչ հավանական է:

Տիեզերական բարդություն

O (1), քանի որ օգտագործվում է միայն անընդհատ տարածություն: