بزرگترین عنصر Kth در Array Leetcode Solutions


سطح دشواری متوسط
اغلب در خشت آمازون سیب ByteDance ای بی Expedia فیس بوک گوگل لینک مایکروسافت وحی Salesforce Spotify آزمایشگاه های والمارت
صف تفرقه بینداز و حکومت کن پشته

در این مشکل ، ما باید بزرگترین عنصر kth را در یک بازگردانیم مرتب نشده صف. توجه داشته باشید که آرایه می تواند کپی باشد. بنابراین ، ما باید 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 در یک آرایه مرتب نشده

برنامه 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)، همانطور که باید آرایه را مرتب کنیم. N = اندازه آرایه

پیچیدگی فضا

O (1) ، همانطور که از فضای ثابت استفاده می کنیم. توجه داشته باشید: مرتب سازی() تابع می تواند استفاده کند بر) حافظه ولی همیشه موضوع این نیست.

رویکرد (انتخاب سریع)

همانطور که در رویکرد قبلی خود بحث کردیم ، فقط باید موارد را پیدا کنیم بازگشت بزرگترین عنصر در آرایه. به روشی ساده ، ما به (n - k + 1) کوچکترین عنصر آرایه نیاز داریم. صحبت از مرتب سازی ، می توانیم به آن فکر کنیم مرتب کردن، که رویکرد مشابهی دارد. در quicksort ، در حالی که انتخاب یک محور، اطمینان حاصل می کنیم که پس از پارتیشن به شاخص صحیح خود در آرایه برسد.

چه می شود اگر ، ما یک تقسیم بندی مشابه انجام دهیم تا (n - k) th index مقدار صحیح خود را بدست می آورد. این همان کاری است که ما می خواهیم در این روش انجام دهیم:

بزرگترین عنصر Kth در یک آرایه مرتب نشده Leetcode Solutions

محوری تصادفی انتخاب کرده و آرایه اطراف آن را تقسیم کنید. اگر به شاخص مورد نظر ما برسد (n - k). سپس ، این بزرگترین عنصر Kth است. در غیر این صورت ، ما می دانیم که شاخص مورد نیاز یا در سمت چپ آن یا در سمت راست آن قرار دارد. سپس می توانیم با تقسیم بندی() تابع مربوطه زیر مجموعه برای یافتن شاخص مورد نیاز ، و بنابراین ، مقدار آن.

اما ، آیا روش فوق مطمئناً بهتر از رویکرد است مرتب سازی یکی؟ ما می دانیم که بدترین حالت quicksort زمانی اتفاق می افتد که کوچکترین / بزرگترین عنصر را به عنوان محور خود انتخاب کنیم ،

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

و زیرمشکل تقریباً همان مسئله است و باعث پیچیدگی زمان O (N * N) می شود. به طور مشابه ، عملکرد پارتیشن ما می تواند چنین تماس هایی را برقرار کند. برای حل این مسئله ، اطمینان حاصل خواهیم کرد که a تصادفی محور در هر نقطه از پارتیشن بندی.

الگوریتم

  1. ایجاد یک QuickSelect () تابعی که مقدار (N - K) را برمی گرداندکوچکترین”عنصر
  2. ایجاد یک تقسیم بندی() تابع کمکی که نمایه صحیح هر را برمی گرداند به صورت تصادفی محوری انتخاب شده
  3. اکنون ، تا زمانی که به نقطه ای برسیم که تقسیم بندی() شاخص برابر با 'را برمی گرداندK':
    • فراخوانی پارتیشن () در a تصادفی محور
    • اگر شاخص محوری برگشت همان باشد K
      • عنصر محوری را برگردانید
    • اگر شاخص چرخش برگشتی کمتر از باشد K
      • فراخوانی پارتیشن () روشن است راست زیر مجموعه از شاخص محوری
    • اگر شاخص محوری برگشت داده شود بیش از است K
      • فراخوانی پارتیشن () روشن است زیر مجموعه آراسته از شاخص محوری
  4. حالا که QuickSelect () شاخص (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 در یک آرایه مرتب نشده

پیچیدگی زمان

رابطه عود را می توان به صورت (N = اندازه آرایه):

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

زیرا انتظار داریم که یک محوری که به طور تصادفی انتخاب شده آرایه را به دو نیمه تقسیم کرده است. بر اساس آن ، می توان پیچیدگی را تقریباً برآورد کرد T (N) = 2N - logN = ~ O (N).

بنابراین ، الگوریتم خطی است. با این حال ، در بدترین حالت ، هنگامی که محورهای تصادفی انتخاب شده بزرگترین / کوچکترین در آرایه هستند ، Time Complexity O (N * N) اما در آرایه ای با اندازه بزرگ احتمال وقوع آن بسیار کم است.

پیچیدگی فضا

O (1) ، زیرا فقط از فضای ثابت استفاده می شود.