ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨਜ਼ ਵਿੱਚ Kth ਸਭ ਤੋਂ ਵੱਡਾ ਤੱਤ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਅਡੋਬ ਐਮਾਜ਼ਾਨ ਸੇਬ ਬਾਈਟਡੈਂਸ ਈਬੇ ਇਕਸਪੀਡੀਆ ਫੇਸਬੁੱਕ ਗੂਗਲ ਸਬੰਧਤ Microsoft ਦੇ ਓਰੇਕਲ Salesforce Spotify ਵਾਲਮਾਰਟ ਲੈਬ
ਅਰੇ ਵੰਡੋ ਅਤੇ ਜਿੱਤੋ Apੇਰ

ਇਸ ਸਮੱਸਿਆ ਵਿੱਚ, ਸਾਨੂੰ ਇੱਕ ਵਿੱਚ 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 ਦੇ ਸਭ ਤੋਂ ਵੱਡੇ ਤੱਤ ਨੂੰ ਲੱਭਣ ਲਈ ਐਲਗੋਰਿਦਮ ਨੂੰ ਲਾਗੂ ਕਰਨਾ

ਸੀ ++ ਪ੍ਰੋਗਰਾਮ

#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), ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਨਿਰੰਤਰ ਜਗ੍ਹਾ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹਾਂ. ਸੂਚਨਾ: ਲੜੀਬੱਧ () ਫੰਕਸ਼ਨ ਵਰਤ ਸਕਦੇ ਹੋ ਓ (ਐਨ) ਮੈਮੋਰੀ ਪਰ ਇਹ ਹਮੇਸ਼ਾ ਨਹੀਂ ਹੁੰਦਾ.

ਪਹੁੰਚ (ਤਤਕਾਲ ਚੋਣ)

ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਆਪਣੇ ਪਿਛਲੇ approachੰਗ ਨਾਲ ਵਿਚਾਰਿਆ ਹੈ, ਸਾਨੂੰ ਬੱਸ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ kth ਐਰੇ ਦਾ ਸਭ ਤੋਂ ਵੱਡਾ ਤੱਤ. ਸਰਲ ਤਰੀਕੇ ਨਾਲ, ਸਾਨੂੰ ਐਰੇ ਵਿਚਲੇ (n - k + 1) ਵੇਂ ਛੋਟੇ ਤੱਤ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਲੜੀਬੱਧ ਬਾਰੇ ਗੱਲ ਕਰਦਿਆਂ, ਅਸੀਂ ਸੋਚ ਸਕਦੇ ਹਾਂ ਕੁਇੱਕੋਰਟ, ਜਿਸ ਦੀ ਇਕੋ ਜਿਹੀ ਪਹੁੰਚ ਹੈ. ਕੁਇੱਕੋਰਟ ਵਿੱਚ, ਜਦੋਂ ਕਿ ਇੱਕ ਦੀ ਚੋਣ ਕਰਦੇ ਹੋ ਧੁੰਦ, ਅਸੀਂ ਇਹ ਸੁਨਿਸ਼ਚਿਤ ਕਰਦੇ ਹਾਂ ਕਿ ਇਹ ਭਾਗ ਤੋਂ ਬਾਅਦ ਐਰੇ ਵਿਚ ਇਸ ਦੇ ਸਹੀ ਸੂਚਕਾਂਕ ਤੇ ਪਹੁੰਚ ਗਿਆ.

ਕੀ ਜੇ, ਜਦ ਤੱਕ ਅਸੀਂ ਇਕੋ ਜਿਹਾ ਵਿਭਾਜਨ ਕੀਤਾ (n - ਕੇ) th ਇੰਡੈਕਸ ਨੂੰ ਇਸਦੇ ਸਹੀ ਮੁੱਲ ਮਿਲਦੇ ਹਨ. ਇਹ ਉਹ ਹੈ ਜੋ ਅਸੀਂ ਇਸ ਪਹੁੰਚ ਵਿਚ ਕਰਨ ਜਾ ਰਹੇ ਹਾਂ:

ਅਣ-ਨਿਰਲੇਪਿਤ ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨਜ਼ ਵਿੱਚ Kth ਸਭ ਤੋਂ ਵੱਡਾ ਤੱਤ

ਕੁਝ ਬੇਤਰਤੀਬੇ ਪਾਈਵੋਟ ਚੁਣੋ ਅਤੇ ਇਸ ਦੇ ਆਲੇ ਦੁਆਲੇ ਐਰੇ ਨੂੰ ਵੰਡੋ. ਜੇ ਇਹ ਸੂਚਕਾਂਕ ਨੂੰ ਮਿਲ ਜਾਵੇ ਤਾਂ ਅਸੀਂ ਚਾਹੁੰਦੇ ਹਾਂ (n - ਕੇ). ਫਿਰ, ਇਹ Kth ਵੱਡਾ ਤੱਤ ਹੈ. ਨਹੀਂ ਤਾਂ, ਅਸੀਂ ਜਾਣਦੇ ਹਾਂ ਕਿ ਲੋੜੀਂਦਾ ਸੂਚਕਾਂਕ ਇਸ ਦੇ ਖੱਬੇ ਜਾਂ ਇਸਦੇ ਸੱਜੇ ਪਾਸੇ ਪਿਆ ਹੈ. ਫਿਰ ਅਸੀਂ ਕਾਲ ਕਰ ਸਕਦੇ ਹਾਂ ਭਾਗ () ਅਨੁਸਾਰੀ ਕੰਮ subarray ਲੋੜੀਂਦਾ ਇੰਡੈਕਸ ਲੱਭਣ ਲਈ, ਅਤੇ ਇਸ ਲਈ, ਇਸਦਾ ਮੁੱਲ.

ਪਰ, ਉਪਰੋਕਤ ਪਹੁੰਚ ਨਿਸ਼ਚਤ ਰੂਪ ਤੋਂ ਵਧੀਆ ਹੈ ਲੜੀਬੱਧ ਇਕ? ਅਸੀਂ ਜਾਣਦੇ ਹਾਂ ਕਿ ਕੁਇੱਕੋਰਟ ਦੀ ਸਭ ਤੋਂ ਭੈੜੀ ਸਥਿਤੀ ਉਦੋਂ ਵਾਪਰਦੀ ਹੈ ਜਦੋਂ ਅਸੀਂ ਸਭ ਤੋਂ ਛੋਟੇ / ਸਭ ਤੋਂ ਵੱਡੇ ਤੱਤ ਨੂੰ ਆਪਣੇ ਮੁੱਖ ਨੂੰ ਚੁਣਦੇ ਹਾਂ ਜਿਵੇਂ ਕਿ ਉਸ ਸਥਿਤੀ ਵਿੱਚ,

ਟੀ (ਐਨ) = ਟੀ (ਐਨ - 1) + ਓ (1)

ਅਤੇ ਸਬਪ੍ਰਬਲਮ ਤਕਰੀਬਨ ਸਮੱਸਿਆ ਦੇ ਸਮਾਨ ਹੈ, ਜਿਸ ਨਾਲ O (N * N) ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਪੈਦਾ ਹੁੰਦੀ ਹੈ. ਇਸੇ ਤਰ੍ਹਾਂ, ਸਾਡਾ ਭਾਗ ਫੰਕਸ਼ਨ ਅਜਿਹੀਆਂ ਕਾਲਾਂ ਕਰ ਸਕਦਾ ਹੈ. ਇਸ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ, ਅਸੀਂ ਇਹ ਸੁਨਿਸ਼ਚਿਤ ਕਰਾਂਗੇ ਕਿ ਅਸੀਂ ਇੱਕ ਬੇਤਰਤੀਬੇ ਵਿਭਾਜਨ ਦੇ ਹਰੇਕ ਬਿੰਦੂ ਤੇ ਮੁੱਖ.

ਐਲਗੋਰਿਥਮ

  1. ਇੱਕ ਬਣਾਓ ਕੁੱਕਸਿਲੈਕਟ () ਫੰਕਸ਼ਨ ਜੋ (ਐਨ - ਕੇ) ਨੂੰ ਵਾਪਸ ਕਰ ਦਿੰਦਾ ਹੈਛੋਟਾ”ਤੱਤ
  2. ਇੱਕ ਬਣਾਓ ਭਾਗ () ਸਹਾਇਕ ਕਾਰਜ ਜੋ ਕਿ ਕਿਸੇ ਦਾ ਸਹੀ ਸੂਚਕਾਂਕ ਵਾਪਸ ਕਰ ਦੇਵੇਗਾ ਲਗਾਤਾਰ ਚੁਣਿਆ ਪਿਵੋਟ
  3. ਹੁਣ, ਜਦ ਤੱਕ ਅਸੀਂ ਉਸ ਬਿੰਦੂ ਤੇ ਨਹੀਂ ਪਹੁੰਚਦੇ ਜਿੱਥੇ ਭਾਗ () ਇੰਡੈਕਸ 'ਦੇ ਬਰਾਬਰ ਵਾਪਸ ਕਰਦਾ ਹੈK':
    • 'ਤੇ ਕਾਲ ਪਾਰਟੀਸ਼ਨ () ਬੇਤਰਤੀਬੇ ਧੁੰਦ
    • ਜੇ ਪਿਵੋਟ ਇੰਡੈਕਸ ਵਾਪਸ ਆ ਗਿਆ ਹੈ K
      • ਪਿਵੋਟ ਐਲੀਮੈਂਟ ਵਾਪਸ ਕਰੋ
    • ਹੋਰ ਜੇ ਪਿਵੋਟ ਇੰਡੈਕਸ ਘੱਟ ਹੈ K
      • ਕਾਲ ਭਾਗ () ਚਾਲੂ ਸੱਜੇ subarray ਪਿਵੋਟ ਇੰਡੈਕਸ ਦਾ
    • ਹੋਰ ਜੇ ਪਿਵੋਟ ਇੰਡੈਕਸ ਵਾਪਸ ਆਇਆ ਤਾਂ ਹੋਰ 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), ਜਿਵੇਂ ਕਿ ਸਿਰਫ ਨਿਰੰਤਰ ਥਾਂ ਵਰਤੀ ਜਾਂਦੀ ਹੈ.