Array Leetcode Solutions में Kth सबसे बड़ा तत्व


कठिनाई स्तर मध्यम
में अक्सर पूछा एडोब वीरांगना सेब ByteDance ईबे Expedia Facebook गूगल लिंक्डइन माइक्रोसॉफ्ट ओरेकल Salesforce Spotify वॉलमार्ट लैब्स
ऐरे विभाजन और जीत ढेर

इस समस्या में, हमें kth सबसे बड़े तत्व को एक में वापस करना होगा अवर्गीकृत सरणी। ध्यान दें कि सरणी में डुप्लिकेट हो सकते हैं। इसलिए, हमें इसे ढूंढना होगा कथ क्रमबद्ध क्रम में सबसे बड़ा तत्व, विशिष्ट 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

जटिलता एक सरणी में Kth सबसे बड़ा तत्व खोजने की जटिलता विश्लेषण

समय जटिलता

O (NlogN), क्योंकि हमें सरणी को क्रमबद्ध करने की आवश्यकता है। एन = सरणी का आकार

अंतरिक्ष की जटिलता

ओ (1), जैसा कि हम निरंतर स्थान का उपयोग करते हैं। नोट: क्रमबद्ध करें () फ़ंक्शन का उपयोग कर सकते हैं पर) स्मृति। लेकिन हमेशा ऐसा ही नहीं होता है।

दृष्टिकोण (त्वरित चयन)

जैसा कि हमने अपने पिछले दृष्टिकोण में चर्चा की है, हमें सिर्फ खोजने की जरूरत है केथ सरणी में सबसे बड़ा तत्व। सरल तरीके से, हमें सरणी में (n - k + 1) वें सबसे छोटा तत्व चाहिए। सॉर्ट के बारे में बात करते हुए, हम सोच सकते हैं जल्दी से सुलझाएं, जिसका दृष्टिकोण समान है। क्विकॉर्ट में, जबकि एक का चयन धुरी, हम यह सुनिश्चित करते हैं कि विभाजन के बाद यह सरणी में अपने सही सूचकांक के लिए जाता है।

क्या होगा अगर, हमने तब तक एक समान विभाजन किया था (एन - के) वें सूचकांक को इसका सही मूल्य मिलता है। इस दृष्टिकोण में हम यही करने जा रहे हैं:

एक अंतहीन सरणी Leetcode समाधान में Kth सबसे बड़ा तत्व

कुछ यादृच्छिक धुरी चुनें और इसके चारों ओर सरणी को विभाजित करें। यदि यह इंडेक्स में हमारी इच्छा (n - k) के लिए जाता है। फिर, यह Kth सबसे बड़ा तत्व है। अन्यथा, हम जानते हैं कि आवश्यक सूचकांक या तो इसके बाईं ओर स्थित है या इसके दाईं ओर। हम तो कॉल कर सकते हैं विभाजन () इसी में कार्य करते हैं सबर्रे आवश्यक सूचकांक खोजने के लिए, और इसलिए, इसका मूल्य।

लेकिन, उपरोक्त दृष्टिकोण निश्चित रूप से की तुलना में बेहतर है छँटाई एक? हम जानते हैं कि क्विकर का सबसे खराब मामला तब होता है जब हम उस मामले में अपनी धुरी के रूप में सबसे छोटे / सबसे बड़े तत्व को चुनते हैं,

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

और उपप्रकार लगभग समस्या के समान है, जिससे ओ (एन * एन) समय की जटिलता होती है। इसी तरह, हमारे विभाजन फ़ंक्शन ऐसी कॉल कर सकते हैं। इसे हल करने के लिए, हम यह सुनिश्चित करेंगे कि हम एक का चयन करें बिना सोचे समझे विभाजन के हर बिंदु पर धुरी।

कलन विधि

  1. बनाओ तुरंत चयन() फ़ंक्शन जो एन (K - K) वें को लौटाता हैसबसे छोटातत्व
  2. बनाओ विभाजन () हेल्पर फंक्शन जो किसी के सही इंडेक्स को लौटाएगा बेतरतीब ढंग से चुना धुरी
  3. अब, जब तक हम उस बिंदु तक नहीं पहुंच जाते हैं विभाजन () सूचकांक 'के बराबर देता हैK':
    • कॉल विभाजन () a पर बिना सोचे समझे धुरी
    • यदि पिवट इंडेक्स लौटाया गया है तो जैसा है 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

जटिलता एक सरणी में Kth सबसे बड़ा तत्व खोजने की जटिलता विश्लेषण

समय जटिलता

पुनरावृत्ति संबंध के रूप में व्यक्त किया जा सकता है (सरणी का एन = आकार):

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

क्योंकि हम उम्मीद करते हैं कि बेतरतीब ढंग से चुनी गई धुरी ने सरणी को दो हिस्सों में विभाजित किया है। इसके आधार पर, जटिलता का अनुमान लगाया जा सकता है टी (एन) = 2 एन - लॉगएन = ~ ओ (एन)।

तो, एल्गोरिथ्म रैखिक है। हालांकि, सबसे खराब स्थिति में, जब चुने गए यादृच्छिक पिवोट्स सरणी में सबसे बड़े / सबसे छोटे होते हैं, तो टाइम कॉम्प्लेक्सिटी बन जाता है ओ (एन * एन)। लेकिन एक बड़े आकार के सरणी में, ऐसा होने की संभावना बहुत कम है।

अंतरिक्ष की जटिलता

ओ (1), चूंकि केवल निरंतर स्थान का उपयोग किया जाता है।