ارے لیٹکوڈ حل میں Kth کا سب سے بڑا عنصر


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایڈوب ایمیزون ایپل ByteDance ای بے Expedia فیس بک گوگل لنکڈ مائیکروسافٹ اوریکل 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 کا سب سے بڑا عنصر تلاش کرنے کے لئے الگورتھم کا نفاذ

سی ++ پروگرام

#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)، جیسا کہ ہمیں صف کو ترتیب دینے کی ضرورت ہے۔ N = سرنی کا سائز

خلائی پیچیدگی

O (1) ، چونکہ ہم مستقل جگہ استعمال کرتے ہیں۔ نوٹ: ترتیب دیں() تقریب استعمال کر سکتے ہیں O (N) یاداشت. لیکن ہمیشہ ایسا نہیں ہوتا ہے۔

نقطہ نظر (فوری انتخاب)

جیسا کہ ہم نے اپنے سابقہ ​​نقطہ نظر میں تبادلہ خیال کیا ، ہمیں صرف اس کو تلاش کرنے کی ضرورت ہے kth صف میں سب سے بڑا عنصر. آسان طریقے سے ، ہمیں صف میں (n - k + 1) ویں سب سے چھوٹے عنصر کی ضرورت ہے۔ ترتیب کے بارے میں بات کرتے ہوئے ، ہم سوچ سکتے ہیں کوئیکسورٹ، جس کا ایک ایسا ہی نقطہ نظر ہے۔ کوئکسورٹ میں ، جبکہ ایک کا انتخاب کرتے ہیں محور، ہم اس بات کو یقینی بناتے ہیں کہ تقسیم کے بعد صف میں اس کی صحیح فہرست ہوجائے گی۔

کیا ہوگا ، جب تک ہم نے اسی طرح کی تقسیم کردیn - k) ویں انڈیکس کو اس کی صحیح قدر ملتی ہے۔ ہم اس نقطہ نظر میں یہی کام کرنے جارہے ہیں۔

غیر ترتیب شدہ صف والے لیٹکوڈ حل میں Kth کا سب سے بڑا عنصر

کچھ بے ترتیب محور کا انتخاب کریں اور اس کے چاروں طرف صف کو تقسیم کریں۔ اگر یہ انڈیکس تک آجاتا ہے تو ہماری خواہش (n - k) ہے۔ پھر ، یہ Kth کا سب سے بڑا عنصر ہے۔ ورنہ ، ہم جانتے ہیں کہ مطلوبہ اشاریہ یا تو اس کے بائیں یا اس کے دائیں طرف ہے۔ اس کے بعد ہم اس کو کال کرسکتے ہیں تقسیم () اسی میں کام subarray مطلوبہ انڈیکس کو تلاش کرنے کے ل. ، اور اس وجہ سے ، اس کی قیمت۔

لیکن ، مندرجہ بالا نقطہ نظر یقینی طور پر بہتر ہے چھانٹ ایک ہم جانتے ہیں کہ کوئکسورٹ کی بدترین صورت اس وقت ہوتی ہے جب ہم اپنے محور کی طرح سب سے چھوٹے / سب سے بڑے عنصر کو چنتے ہیں ،

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

اور سب پروبلیوش تقریبا as پریشانی کی طرح ہی ہے ، جس کی وجہ سے O (N * N) وقت کی پیچیدگی ہوتی ہے۔ اسی طرح ، ہمارے تقسیم کا فنکشن اس طرح کی کال کر سکتا ہے۔ اس کو حل کرنے کے ل we ، ہم اس بات کو یقینی بنائیں گے کہ ہم کسی کا انتخاب کریں بے ترتیب تقسیم کے ہر مقام پر محور

الگورتھم

  1. ایک تخلیق کریں کوئیک سلیکٹ () فنکشن جو (N - K) کو واپس کرتا ہے “سب سے چھوٹی”عنصر
  2. ایک تخلیق کریں تقسیم () مددگار فنکشن جو کسی کا صحیح انڈیکس واپس کرے گا تصادفی منتخب محور
  3. اب ، یہاں تک کہ ہم اس مقام پر پہنچیں جہاں تقسیم () کے برابر انڈیکس لوٹاتا ہےK':
    • کال پارٹیشن () پر بے ترتیب محور
    • اگر پیوٹ انڈیکس لوٹ آیا ہے تو K
      • محور عنصر کو واپس کریں
    • دوسری صورت میں اگر پییوٹ انڈیکس لوٹ گیا تو اس سے کم ہے K
      • کال پارٹیشن () آن ٹھیک ہے subarray محور اشاریہ کا
    • بصورت دیگر اگر محور انڈیکس لوٹ گیا تو اس سے زیادہ ہے K
      • کال پارٹیشن () آن بائیں subarray محور اشاریہ کا
  4. اب جب کہ کوئیک سلیکٹ () (N - K) ویں انڈیکس کو واپس کردیا ہے ، نتیجہ پرنٹ کریں

غیر ترتیب شدہ صف میں 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 کے سب سے بڑے عنصر کی تلاش کا پیچیدہ تجزیہ

وقت کی پیچیدگی

تکرار کے رشتے کو بطور اظہار کیا جاسکتا ہے (N = سرنی کا سائز):

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

کیونکہ ہم توقع کرتے ہیں کہ تصادفی طور پر منتخب محور نے سرنی کو دو حصوں میں تقسیم کردیا۔ اس کی بنیاد پر ، پیچیدگی کا اندازہ لگایا جاسکتا ہے ٹی (این) = 2N - logN = ~ O (N)

تو ، الگورتھم لکیری ہے. تاہم ، بدترین صورت میں ، جب منتخب کردہ بے ترتیب محور سب سے بڑے / چھوٹے سب سے چھوٹے ہوتے ہیں تو ، ٹائم کمپلیکس بن جاتا ہے O (N * N) لیکن بڑے سائز میں ، اس کے ہونے کا امکان بہت کم ہے۔

خلائی پیچیدگی

O (1) ، چونکہ صرف مستقل جگہ استعمال ہوتی ہے۔