በ “Array Leetcode Solutions” ውስጥ Kth ትልቁ አካል


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን ፓም ByteDance eBay Expedia ፌስቡክ google LinkedIn የ Microsoft በ Oracle Salesforce Spotify የዎልማርት ላብራቶሪዎች
ሰልፍ አካፍል እና ድል እከክ

በዚህ ችግር ውስጥ በ k ውስጥ ትልቁን ንጥረ ነገር መመለስ አለብን ያልተጠበቁ ደርድር. ድርድሩ ብዜቶች ሊኖረው እንደሚችል ልብ ይበሉ። ስለዚህ ፣ እኛ ማግኘት አለብን ኬት ትልቁ ንጥረ ነገር በተደረደረው ቅደም ተከተል እንጂ የተለየ የ Kth ትልቁ አካል አይደለም።

ለምሳሌ

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

አቀራረብ (የመደርደር ድርድር)

ይህ አካሄድ ቀጥታ ወደ ፊት ነው ፡፡ መላውን ድርድር ደርድር። እና አሁን በምድቡ ውስጥ ማንኛውንም ትልቅ አካል መናገር ይችላሉ። ግን ፣ እኛ ብቻ መፈለግ ብቻ በቂ ነው ኬት ትልቁ ንጥረ ነገር. ለዚያም ነው የተሻለ አካሄድን ማምጣት የምንችለው ፡፡

አልጎሪዝም

  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';
}

የጃቫ ፕሮግራም

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

ባልተስተካከለ ድርድር ውስጥ የኬትን ትልቁን ንጥረ ነገር ለማግኘት ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (NlogN), ድርድርን ለመደርደር እንደፈለግን. N = የድርድሩ መጠን

የቦታ ውስብስብነት

ኦ (1) ፣ የማያቋርጥ ቦታ እንደምንጠቀም. ማስታወሻ: ደርድር () ተግባር መጠቀም ይችላል ኦ (ኤን) ማህደረ ትውስታ. ግን ያ ሁልጊዜ አይደለም ፡፡

አቀራረብ (በፍጥነት መምረጥ)

በቀደመው አካሄዳችን እንደተነጋገርነው እኛ ማግኘት ያለብን ብቻ ነው kth በምድቡ ውስጥ ትልቁ ንጥረ ነገር። በቀላል መንገድ በድርድሩ ውስጥ (n - k + 1) ኛ ትንሹን ንጥረ ነገር እንፈልጋለን። ስለ ዓይነት ማውራት ፣ ማሰብ እንችላለን ፈጣን, ተመሳሳይ አቀራረብ ያለው. በፍጥነት በሚመረጥ ሁኔታ ፣ ሀን በሚመርጡበት ጊዜ ምሰሶከመከፋፈሉ በኋላ በድርድሩ ውስጥ ወደ ሚገኘው ትክክለኛ መረጃ ጠቋሚ መድረሱን እናረጋግጣለን ፡፡

ቢሆንስ ፣ እስከ (እስከn - k) ኛ ማውጫ ትክክለኛውን ዋጋ ያገኛል። በዚህ አቀራረብ ውስጥ ምን እናደርጋለን-

ባልተስተካከለ የ Leetcode Solutions ውስጥ Kth ትልቁ አካል

የተወሰኑ የዘፈቀደ ምሰሶዎችን ይምረጡ እና በዙሪያው ያለውን ድርድር ይከፋፍሉ። ወደምንፈልገው መረጃ ጠቋሚ ከደረሰ (n - k) ፡፡ ከዚያ ፣ ይህ የ Kth ትልቁ አካል ነው። አለበለዚያ የሚፈለገው መረጃ ጠቋሚ ወይ ከግራው ወይም ከቀኙ እንደሚገኝ እናውቃለን ፡፡ ከዚያ መደወል እንችላለን ክፍልፍል () በተጓዳኙ ውስጥ ተግባር ሰርጓጅ አስፈላጊውን መረጃ ጠቋሚ ለማግኘት እና ስለዚህ ዋጋውን ፡፡

ግን ፣ ከላይ የተጠቀሰው አካሄድ በእርግጥ ከ ‹የተሻለ› ነው መደርደር አንድ? እንደዚያ ሁኔታ ትንሹን / ትልቁን ንጥረ ነገር እንደ ምሰሶችን ስንመርጥ በጣም የከፋ ፈጣን የፍጥነት ሁኔታ እንደሚከሰት እናውቃለን ፣

ቲ (ኤን) = ቲ (N - 1) + ኦ (1)

እና ንዑስ ችግሩ ከችግሩ ጋር ተመሳሳይ ነው ፣ ይህም የኦ (N * N) የጊዜ ውስብስብነትን ያስከትላል ፡፡ በተመሳሳይ ሁኔታ የእኛ የመከፋፈያ ተግባር እንደዚህ ዓይነት ጥሪዎችን ሊያደርግ ይችላል ፡፡ ይህንን ለመፍታት ሀን የመረጥን መሆኑን እናረጋግጣለን ያለብለኀት በእያንዳንዱ የመለያያ ነጥብ ምሰሶ ፡፡

አልጎሪዝም

  1. ፍጠር ፈጣን ይምረጡ () (N - K) ኛን የሚመልስ ተግባርበጣም ትንሽ”አባል
  2. ፍጠር ክፍልፍል () የማንኛውንም ትክክለኛውን መረጃ ጠቋሚ የሚመልስ ረዳት ተግባር በዘፈቀደ የተመረጠ ምሰሶ
  3. አሁን የት ድረስ እስከምንደርስ ድረስ ክፍልፍል () መረጃ ጠቋሚውን ከ 'ጋር እኩል ይመልሳልK':
    • የጥሪ ክፍፍል () በ ላይ ያለብለኀት ምሰሶ
    • የምስሶ መረጃ ጠቋሚ ከተመለሰ እንደ ተመሳሳይ ነው K
      • የምሰሶውን አካል ይመልሱ
    • ሌላ የምሰሶ ማውጫ ከተመለሰ ከዚህ ያነሰ ነው K
      • የጥሪ ክፍፍል () በርቷል ቀኝ ሰርጓጅ የምስሶ ማውጫ
    • ሌላ የምሰሶ ማውጫ ከተመለሰ የበለጠ ነው K
      • የጥሪ ክፍፍል () በርቷል ግራ ሰርጓጅ የምስሶ ማውጫ
  4. አሁን አንግዲህ ፈጣን ይምረጡ () የ (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';
}

የጃቫ ፕሮግራም

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

ባልተስተካከለ ድርድር ውስጥ የኬትን ትልቁን ንጥረ ነገር ለማግኘት ውስብስብነት ትንተና

የጊዜ ውስብስብነት

የተደጋጋሚነት ግንኙነቱ እንደ (N = የአቀማመጥ መጠን):

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

ምክንያቱም በዘፈቀደ የተመረጠ ምሰሶ ድርድርን ወደ ሁለት ግማሽ ከፍሏል ብለን እንጠብቃለን። በእሱ ላይ በመመርኮዝ ውስብስብነቱ በግምት እንደ ሊገመት ይችላል ቲ (ኤን) = 2N - logN = ~ O (N) ፡፡

ስለዚህ ፣ አልጎሪዝም መስመራዊ ነው። ሆኖም ፣ በጣም በከፋ ሁኔታ ውስጥ ፣ የተመረጡት የዘፈቀደ ምሰሶዎች በድርድሩ ውስጥ ሁሉም ትልቅ / ትንሽ ሲሆኑ ፣ የጊዜ ውስብስብ ይሆናል ኦ (N * N) ፡፡ ነገር ግን በትላልቅ መጠን ድርድር ውስጥ መከሰት በጣም አናሳ ነው።

የቦታ ውስብስብነት

ኦ (1) ፣ እንደ ቋሚ ቦታ ብቻ ጥቅም ላይ ይውላል ፡፡