ஒரு வரிசை லீட்கோட் தீர்வுகளில் Kth மிகப்பெரிய உறுப்பு


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ஆப்பிள் ByteDance ஈபே Expedia பேஸ்புக் கூகிள் லின்க்டு இன் மைக்ரோசாப்ட் ஆரக்கிள் விற்பனைக்குழு வீடிழந்து வால்மார்ட் ஆய்வகங்கள்
அணி பிரித்து வெல்லுங்கள் குவியல்

இந்த சிக்கலில், நாம் ஒரு இல் உள்ள kth மிகப்பெரிய உறுப்பை திருப்பித் தர வேண்டும் வரிசைப்படுத்தப்படாதது வரிசை. வரிசைக்கு நகல்கள் இருக்கலாம் என்பதை நினைவில் கொள்க. எனவே, நாம் கண்டுபிடிக்க வேண்டும் 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 மிகப்பெரிய உறுப்பைக் கண்டுபிடிக்க வழிமுறையை செயல்படுத்துதல்

சி ++ திட்டம்

#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

வரிசைப்படுத்தப்படாத வரிசையில் Kth மிகப்பெரிய உறுப்பைக் கண்டுபிடிப்பதற்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

O (NlogN), நாம் வரிசையை வரிசைப்படுத்த வேண்டும். N = வரிசையின் அளவு

விண்வெளி சிக்கலானது

ஓ (1), நாம் நிலையான இடத்தைப் பயன்படுத்துகிறோம். குறிப்பு: வகைபடுத்து() செயல்பாடு பயன்படுத்தலாம் ஓ (என்) நினைவு. ஆனால் அது எப்போதுமே அப்படி இருக்காது.

அணுகுமுறை (விரைவான தேர்வு)

எங்கள் முந்தைய அணுகுமுறையில் நாங்கள் விவாதித்தபடி, நாம் அதைக் கண்டுபிடிக்க வேண்டும் kth வரிசையில் மிகப்பெரிய உறுப்பு. எளிமையான வழியில், வரிசையில் (n - k + 1) வது சிறிய உறுப்பு தேவை. வரிசையைப் பற்றி பேசுகையில், நாம் சிந்திக்கலாம் குவிகார்ட், இது போன்ற அணுகுமுறையைக் கொண்டுள்ளது. புதைமணலில், ஒரு தேர்ந்தெடுக்கும்போது மையம், பகிர்வுக்குப் பிறகு அது வரிசையில் அதன் சரியான குறியீட்டைப் பெறுவதை உறுதிசெய்கிறோம்.

என்ன என்றால், நாங்கள் இதேபோன்ற பகிர்வு செய்தோம் (n - கே) வது குறியீடு அதன் சரியான மதிப்பைப் பெறுகிறது. இந்த அணுகுமுறையில் இதைத்தான் நாங்கள் செய்யப்போகிறோம்:

வரிசைப்படுத்தப்படாத வரிசை லீட்கோட் தீர்வுகளில் Kth மிகப்பெரிய உறுப்பு

சில சீரற்ற பிவோட்டைத் தேர்ந்தெடுத்து அதைச் சுற்றியுள்ள வரிசையைப் பிரிக்கவும். அது நாம் விரும்பும் குறியீட்டுக்கு வந்தால் (n - k). பின்னர், இது Kth மிகப்பெரிய உறுப்பு ஆகும். இல்லையெனில், தேவையான குறியீட்டு அதன் இடதுபுறத்தில் அல்லது வலதுபுறத்தில் உள்ளது என்பதை நாங்கள் அறிவோம். நாம் பின்னர் அழைக்கலாம் பகிர்வு () தொடர்புடைய செயல்பாடு subarray தேவையான குறியீட்டைக் கண்டுபிடிக்க, எனவே, அதன் மதிப்பு.

ஆனால், மேற்கண்ட அணுகுமுறை நிச்சயமாக விட சிறந்தது வரிசைப்படுத்த ஒன்று? அந்த விஷயத்தில் உள்ளதைப் போலவே மிகச்சிறிய / மிகப் பெரிய உறுப்பை எங்கள் மையமாகத் தேர்ந்தெடுக்கும்போது புதைமணலின் மோசமான நிலை ஏற்படுகிறது என்பதை நாங்கள் அறிவோம்,

டி (என்) = டி (என் - 1) + ஓ (1)

மற்றும் துணைப் பிரச்சினை கிட்டத்தட்ட சிக்கலைப் போன்றது, இதனால் O (N * N) நேர சிக்கலை ஏற்படுத்துகிறது. இதேபோல், எங்கள் பகிர்வு செயல்பாடு அத்தகைய அழைப்புகளை செய்யலாம். இதைத் தீர்க்க, நாங்கள் ஒரு தேர்வு செய்வதை உறுதி செய்வோம் சீரற்ற பகிர்வின் ஒவ்வொரு கட்டத்திலும் முன்னிலை.

அல்காரிதம்

  1. உருவாக்கவும் விரைவு தேர்வு () (N - K) வது “சிறிய”உறுப்பு
  2. உருவாக்கவும் பகிர்வு () எந்தவொரு சரியான குறியீட்டையும் வழங்கும் உதவி செயல்பாடு தோராயமாக தேர்ந்தெடுக்கப்பட்ட முன்னிலை
  3. இப்போது, ​​நாம் எங்கு அடையும் வரை பகிர்வு () குறியீட்டை 'க்கு சமமாக வழங்குகிறதுK':
    • அழைப்பு பகிர்வு () a சீரற்ற மையம்
    • திரும்பிய பிவோட் குறியீடு சமமாக இருந்தால் K
      • பிவோட் உறுப்பை திருப்பி விடுங்கள்
    • பிவோட் குறியீட்டு திரும்பியிருந்தால் குறைவாக இருந்தால் K
      • அழைப்பு பகிர்வு () ஆன் வலது subarray மைய குறியீட்டின்
    • பிவோட் குறியீட்டு திரும்பினால் வேறு K
      • அழைப்பு பகிர்வு () ஆன் இடது துணை மைய குறியீட்டின்
  4. இப்போது அந்த விரைவு தேர்வு () (N - K) வது குறியீட்டை வழங்கியுள்ளது, முடிவை அச்சிடுக

வரிசைப்படுத்தப்படாத வரிசையில் Kth மிகப்பெரிய உறுப்பைக் கண்டுபிடிக்க வழிமுறையை செயல்படுத்துதல்

சி ++ திட்டம்

#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

வரிசைப்படுத்தப்படாத வரிசையில் Kth மிகப்பெரிய உறுப்பைக் கண்டுபிடிப்பதற்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

தொடர்ச்சியான உறவை இவ்வாறு வெளிப்படுத்தலாம் (N = வரிசையின் அளவு):

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

ஏனெனில் தோராயமாக தேர்ந்தெடுக்கப்பட்ட முன்னிலை வரிசையை இரண்டு பகுதிகளாகப் பிரிக்கிறது என்று நாங்கள் எதிர்பார்க்கிறோம். அதன் அடிப்படையில், சிக்கலானது தோராயமாக மதிப்பிடப்படுகிறது டி (என்) = 2N - logN = ~ O (N).

எனவே, வழிமுறை நேரியல். இருப்பினும், மிக மோசமான நிலையில், தேர்ந்தெடுக்கப்பட்ட சீரற்ற பிவோட்கள் அனைத்தும் வரிசையில் மிகப்பெரிய / சிறியதாக இருக்கும்போது, ​​நேர சிக்கலானது O (N * N). ஆனால் ஒரு பெரிய அளவிலான வரிசையில், அது நடப்பது மிகக் குறைவு.

விண்வெளி சிக்கலானது

ஓ (1), நிலையான இடம் மட்டுமே பயன்படுத்தப்படுகிறது.