એરે લીટકોડ સોલ્યુશન્સમાં Kth સૌથી મોટું તત્વ


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન ByteDance ઇબે એક્સપેડિયા ફેસબુક Google LinkedIn માઈક્રોસોફ્ટ ઓરેકલ Salesforce Spotify વોલમાર્ટ લેબ્સ
અરે વિભાજીત અને વિજય .ગલો

આ સમસ્યામાં, આપણે an માં kth સૌથી મોટું તત્ત્વ પાછું આપવું પડશે અનસortedર્ટ કરેલું એરે. નોંધ લો કે એરેમાં ડુપ્લિકેટ્સ હોઈ શકે છે. તેથી, આપણે શોધવા પડશે Kth સ Kર્ટ કરેલા ક્રમમાં સૌથી મોટો તત્વ, વિશિષ્ટ Kth સૌથી મોટો તત્વ નહીં.

ઉદાહરણ

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

અભિગમ (સortર્ટિંગ એરે)

આ અભિગમ સીધો આગળ છે. સંપૂર્ણ એરે સortર્ટ કરો. અને હવે તમે એરેમાં કોઈ પણ મોટામાં મોટા ઘટકને કહેવામાં સક્ષમ છો. પરંતુ, તે ફક્ત શોધવા માટે પૂરતું છે Kth સૌથી મોટો તત્વ. તેથી જ આપણે વધુ સારા અભિગમ સાથે આવી શકીએ છીએ.

અલ્ગોરિધમ

  1. એરે સortર્ટ કરો
  2. એરેના પાછળના ભાગથી Kth સૌથી મોટા તત્વને .ક્સેસ કરો
  3. જવાબ છાપો

બિન સortedર્ટ કરેલા એરેમાં 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

અનસortedર્ટ થયેલ એરેમાં Kth સૌથી મોટું તત્વ શોધવાનું જટિલતા વિશ્લેષણ

સમય જટિલતા

O (NlogN), આપણે એરેને સ sortર્ટ કરવાની જરૂર છે. એન = એરેનું કદ

જગ્યાની જટિલતા

ઓ (1), જેમકે આપણે સતત જગ્યા વાપરીએ છીએ. નૉૅધ: સ sortર્ટ () કાર્ય ઉપયોગ કરી શકો છો ઓ (એન) મેમરી. પરંતુ હંમેશા એવું થતું નથી.

અભિગમ (ઝડપી પસંદગી)

જેમ આપણે પહેલાના અભિગમમાં ચર્ચા કરી હતી, આપણે ફક્ત તે શોધવાની જરૂર છે kth એરેમાં સૌથી મોટો તત્વ. સરળ રીતે, અમને એરેમાં (n - k + 1) મી નાના તત્વની જરૂર છે. સ sortર્ટ વિશે વાત કરતા, આપણે વિચારી શકીએ ક્વિક્સર્ટછે, જે સમાન અભિગમ ધરાવે છે. ક્વિક્સર્ટમાં, પસંદ કરતી વખતે પીવટ, અમે ખાતરી કરીએ છીએ કે તે પાર્ટીશન પછી એરેમાં તેના યોગ્ય અનુક્રમણિકા પર પહોંચ્યું છે.

શું જો, અમે ત્યાં સુધી સમાન પાર્ટીશન કર્યું (એન - કે) મી અનુક્રમણિકા તેનું યોગ્ય મૂલ્ય મેળવે છે. આ અભિગમમાં આપણે આ કરવા જઇ રહ્યા છીએ:

બિન સortedર્ટ કરેલા એરે લીટકોડ સોલ્યુશન્સમાં Kth સૌથી મોટું તત્વ

કેટલાક રેન્ડમ પાઇવોટ પસંદ કરો અને તેની આસપાસ એરેને પાર્ટીશન કરો. જો તે અનુક્રમણિકાને મળે છે તો આપણે ઇચ્છા કરીએ છીએ (n - કે). તે પછી, આ Kth સૌથી મોટું તત્વ છે. નહિંતર, આપણે જાણીએ છીએ કે આવશ્યક અનુક્રમણિકા કાં તો તેની ડાબી બાજુ અથવા તેની જમણી બાજુએ આવેલું છે. અમે પછી ક callલ કરી શકો છો ભાગલા () અનુરૂપ કાર્ય સબબ્રે આવશ્યક અનુક્રમણિકા શોધવા માટે, અને તેથી તેનું મૂલ્ય.

પરંતુ, ઉપરોક્ત અભિગમ એ કરતાં ચોક્કસપણે સારી છે સોર્ટિંગ એક? આપણે જાણીએ છીએ કે ક્વિક્સોર્ટનો સૌથી ખરાબ કેસ ત્યારે બને છે જ્યારે આપણે અમારા મુખ્ય તરીકે સૌથી નાના / મહાન તત્વને પસંદ કરીએ છીએ,

ટી (એન) = ટી (એન - 1) + ઓ (1)

અને પેટા પ્રોબ્લેમ લગભગ સમસ્યાનો સમાન છે, ઓ (એન * એન) સમય જટિલતાનું કારણ બને છે. એ જ રીતે, આપણું પાર્ટીશન ફંક્શન આવા ક callsલ્સ કરી શકે છે. આના નિરાકરણ માટે, અમે ખાતરી કરીશું કે આપણે પસંદ કરેલ એક રેન્ડમ પાર્ટીશનના દરેક બિંદુએ ધરી.

અલ્ગોરિધમ

  1. બનાવો ક્વિકસલેક્ટ () ફંક્શન કે જે (એન - કે) મી પાછું આપે છે “સૌથી નાનો”તત્વ
  2. બનાવો ભાગલા () સહાયક કાર્ય જે કોઈની સાચી અનુક્રમણિકા પરત કરશે અવ્યવસ્થિત રીતે પસંદ કરેલ ધરી
  3. હવે, જ્યાં સુધી આપણે ત્યાં પહોંચ્યા ત્યાં સુધી ભાગલા () 'ની બરાબર અનુક્રમણિકા આપે છેK':
    • પર પાર્ટીશન ક callલ કરો () રેન્ડમ પીવટ
    • જો પાઇવટ ઇન્ડેક્સ પાછો આવે તો તે જ છે K
      • ધરી તત્ત્વ પાછા
    • બાકી જો પાઇવટ ઇન્ડેક્સ પાછો આવે તો તે ઓછું છે K
      • ક partitionલ પાર્ટીશન () ચાલુ કરો અધિકાર સબબ્રે પીવટ ઇન્ડેક્સનો
    • બાકી જો પાઇવટ ઇન્ડેક્સ પાછો ફર્યો K
      • ક partitionલ પાર્ટીશન () ચાલુ કરો ડાબું સબબ્રે પીવટ ઇન્ડેક્સનો
  4. હવે ક્વિકસલેક્ટ () (એન - કે) મી અનુક્રમણિકા પરત કરી છે, પરિણામ છાપો

બિન સortedર્ટ કરેલા એરેમાં 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

અનસortedર્ટ થયેલ એરેમાં Kth સૌથી મોટું તત્વ શોધવાનું જટિલતા વિશ્લેષણ

સમય જટિલતા

પુનરાવૃત્તિ સંબંધ તરીકે વ્યક્ત કરી શકાય છે (એન = એરેનું કદ):

ટી (એન) = ટી (એન / 2) + ઓ (એન - 1)

કારણ કે આપણે અપેક્ષા રાખીએ છીએ કે અવ્યવસ્થિત રીતે પસંદ કરેલા ધરીએ એરેને બે ભાગમાં વહેંચ્યો છે. તેના આધારે, જટિલતાનો આશરે અંદાજ લગાવી શકાય છે ટી (એન) = 2 એન - લોગએન = ~ ઓ (એન).

તેથી, અલ્ગોરિધમનો રેખીય છે. જો કે, સૌથી ખરાબ કિસ્સામાં, જ્યારે પસંદ થયેલ રેન્ડમ પાઇવોટ્સ એરેમાં સૌથી મોટા / નાના હોય છે, ત્યારે ટાઇમ કોમ્પ્લેક્સિટી બને છે ઓ (એન * એન) પરંતુ મોટા કદના એરેમાં, તે બનવાની સંભાવના ખૂબ ઓછી છે.

જગ્યાની જટિલતા

ઓ (1), જેમ કે માત્ર સતત જગ્યા વપરાય છે.