अ‍ॅरे लीटकोड सोल्यूशन्समधील केथचा सर्वात मोठा घटक


अडचण पातळी मध्यम
वारंवार विचारले अडोब ऍमेझॉन सफरचंद बाइट डान्स हा कोड eBay यामध्ये फेसबुक Google संलग्न मायक्रोसॉफ्ट ओरॅकल सेल्सबॉल्स Spotify वॉलमार्ट लॅब
अरे विभाजित आणि विजय ढीग

या समस्येमध्ये, आम्हाला एएन मधील सर्वात मोठा घटक परत करावा लागेल अनसॉर्ट अॅरे. लक्षात घ्या की अ‍ॅरेमध्ये डुप्लिकेट असू शकतात. तर, आम्हाला ते शोधावे लागेल 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 सर्वात मोठा घटक शोधण्याचे जटिल विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एनएलजीएन)आपल्याला अ‍ॅरे सॉर्ट करणे आवश्यक आहे. एन = अ‍ॅरेचा आकार

जागेची जटिलता

ओ (1), जसे की आपण निरंतर जागा वापरतो. टीप: क्रमवारी लावा () फंक्शन वापरू शकतो ओ (एन) स्मृती. परंतु नेहमीच असे होत नाही.

दृष्टीकोन (द्रुत निवड)

आमच्या मागील दृष्टिकोनात आपण चर्चा केल्याप्रमाणे, आम्हाला फक्त शोधणे आवश्यक आहे kth अ‍ॅरे मधील सर्वात मोठा घटक. सोप्या मार्गाने, आपल्याला अ‍ॅरेमधील (n - k + 1) व्या सर्वात लहान घटकाची आवश्यकता आहे. क्रमवारी बद्दल बोलत, आम्ही विचार करू शकता क्विझकोर्ट, ज्याचा एक समान दृष्टीकोन आहे. क्विक्शॉर्टमध्ये, निवडताना मुख्यविभाजनानंतर अ‍ॅरेमध्ये त्याची अचूक अनुक्रमणिका झाल्याचे सुनिश्चित करतो.

काय तर, आम्ही पर्यंत असे विभाजन केले (एन - के) व्या निर्देशांकाला त्याचे योग्य मूल्य प्राप्त होते. या दृष्टीकोनातून आपण हे करणार आहोतः

एक अक्रमित अ‍ॅरे लीटकोड सोल्यूशन्समधील कॅथचा सर्वात मोठा घटक

काही यादृच्छिक मुख्य निवडा आणि त्याभोवती अ‍ॅरे विभाजित करा. जर ते अनुक्रमणिकेत पोहोचले तर आम्ही इच्छित आहोत (एन - के). मग हा Kth सर्वात मोठा घटक आहे. अन्यथा, आम्हाला माहित आहे की आवश्यक अनुक्रमणिका त्याच्या डावीकडे किंवा उजवीकडे आहे. आम्ही नंतर कॉल करू शकता विभाजन () संबंधित कार्य सबअरे आवश्यक निर्देशांक शोधण्यासाठी आणि म्हणून त्याचे मूल्य.

परंतु, वरील दृष्टीकोन नक्कीच त्यापेक्षा चांगला आहे वर्गीकरण एक? आम्हाला माहित आहे की जेव्हा आपण सर्वात लहान / सर्वात मोठा घटक आपला मुख्य घटक म्हणून निवडतो त्यावेळेस कोइकोसोर्टची सर्वात वाईट घटना उद्भवते,

टी (एन) = टी (एन - 1) + ओ (1)

आणि सबप्रोब्लम जवळजवळ समस्येसारखेच आहे, ज्यामुळे ओ (एन * एन) वेळ गुंतागुंत होते. त्याचप्रमाणे आपले विभाजन कार्य असे कॉल करू शकते. याचे निराकरण करण्यासाठी आम्ही खात्री करुन घेऊ की आम्ही एक यादृच्छिक विभाजनाच्या प्रत्येक बिंदूवर मुख्य.

अल्गोरिदम

  1. तयार क्विक सिलेक्ट () फंक्शन जे (एन - के) व्या परत करतेसर्वात लहान" घटक
  2. तयार विभाजन () मदतनीस फंक्शन जे कोणाचेही योग्य अनुक्रमणिका परत करेल सहजगत्या निवडलेला मुख्य
  3. आता जिथे आपण पोचतो तिथे विभाजन () निर्देशांक 'च्या बरोबरीने परत करतोK':
    • वर विभाजन () कॉल करा यादृच्छिक मुख्य
    • जर मुख्य सूचकांक परत आला तर तेच आहे K
      • मुख्य घटक परत करा
    • अन्यथा जर पिवोट इंडेक्स परत आला तर त्यापेक्षा कमी आहे K
      • कॉल विभाजन () चालू करा योग्य सबअरे मुख्य निर्देशांक
    • अन्यथा जर पिवोट इंडेक्स परत आला तर त्याहून अधिक आहे K
      • कॉल विभाजन () चालू करा डावा सबरी मुख्य निर्देशांक
  4. आता ते क्विक सिलेक्ट () (एन - के) व्या निर्देशांक परत केला आहे, निकाल प्रिंट करा

क्रमवारी नसलेल्या अ‍ॅरे मधील 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 सर्वात मोठा घटक शोधण्याचे जटिल विश्लेषण

वेळ कॉम्प्लेक्सिटी

पुनरावृत्ती संबंध म्हणून व्यक्त केले जाऊ शकतात (अ‍ॅरेचा एन = आकार):

टी (एन) = टी (एन / 2) + ओ (एन - 1)

कारण आम्हाला अशी अपेक्षा आहे की यादृच्छिकपणे निवडलेल्या धुराने अ‍ॅरेचे दोन भाग केले. त्याच्या आधारे, जटिलतेचा अंदाजे अंदाज लावला जाऊ शकतो टी (एन) = 2 एन - लॉगएन = ~ ओ (एन).

तर, अल्गोरिदम रेषात्मक आहे. तथापि, सर्वात वाईट परिस्थितीत, निवडलेले यादृच्छिक मुख्य मुख्य सर्व अ‍ॅरे मधील सर्वात मोठे / सर्वात लहान असतात तेव्हा टाइम कॉम्प्लेक्सिटी बनते ओ (एन * एन) परंतु मोठ्या आकाराच्या अ‍ॅरेमध्ये हे घडण्याची शक्यता फारच कमी आहे.

जागेची जटिलता

ओ (1), फक्त स्थिर जागा वापरली जाते म्हणून.