Array Leetcode Solutions-da ən böyük element

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma ByteDance eBay Expedia Facebook google LinkedIn microsoft Kahin Salesforce Spotify Walmart Laboratoriyaları
alqoritmlər Geyim kodlaşdırma Bölün və fəth edin Yığın müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 37

Bu problemdə, ən böyük k elementini bir çeşidlənməmiş array. Dizinin təkrarlana biləcəyini unutmayın. Beləliklə, tapmalıyıq Kth sıralanmış qaydada ən böyük element, fərqli Kth ən böyük element deyil.

misal

A = {4 , 2 , 5 , 3 , 1}
K = 2
4
A = {7 , 2 , 6 , 4 , 3 , 5}
K = 4
4

Yanaşma (Sıralama sırası)

Bu yanaşma düz irəliləyir. Bütün serialı çeşidləyin. Və indi serialdakı ən böyük elementi izah edə biləcəksiniz. Ancaq sadəcə tapmaq üçün kifayətdir Kth ən böyük element. Buna görə daha yaxşı bir yanaşma ilə gələ bilərik.

Alqoritm

  1. Dizini sıralayın
  2. Dizinin arxasından Kth ən böyük elementə daxil olun
  3. Cavabı çap edin

Sıralanmamış massivdə Kth ən böyük elementi tapmaq üçün alqoritmin tətbiqi

C ++ Proqramı

#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';
}

Java Proqramı

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

Sıralanmamış bir sıra içərisində Kth ən böyük elementi tapmaq üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (NlogN), serialı sıralamağımız lazım olduğu üçün. N = Massivin ölçüsü

Kosmik mürəkkəblik

O (1), daimi məkandan istifadə etdikcə. Qeyd: növ() funksiyanı istifadə edə bilərsiniz O (N) yaddaş. Ancaq bu həmişə belə deyil.

Yanaşma (sürətli seçin)

Əvvəlki yanaşmamızda müzakirə etdiyimiz kimi, sadəcə tapmaq lazımdır kth massivdəki ən böyük element. Daha sadə şəkildə, massivdəki (n - k + 1) ən kiçik elementə ehtiyacımız var. Sıralama haqqında danışarkən düşünə bilərik qığılcımoxşar bir yanaşmaya sahibdir. Quicksortda, a seçərkən milbölmədən sonra massivdə düzgün göstəriciyə çatmasını təmin edirik.

Nə olarsa, (n - k) indeks düzgün dəyərini alır. Bu yanaşmada edəcəyimiz şey budur:

Sıralanmamış massivdəki K ən böyük element Leetcode SolutionsPin

Təsadüfi bir pivot seçin və massivi ətrafına bölün. İstədiyimiz göstəriciyə çatsa (n - k). Sonra, bu K ən böyük elementdir. Əks təqdirdə, tələb olunan indeksin ya solunda, ya da sağında olduğunu bilirik. Sonra zəng edə bilərik bölmə () müvafiq olaraq fəaliyyət göstərir alt massiv tələb olunan indeksi və buna görə də dəyərini tapmaq.

Ancaq yuxarıdakı yanaşma əlbəttə ki, daha yaxşıdır sıralama bir? Ən pis quicksort vəziyyətinin, bu vəziyyətdə olduğu kimi özümüzün ən kiçik / ən böyük elementi seçdiyimiz zaman baş verdiyini bilirik,

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

və alt problem demək olar ki, problemlə eynidir və O (N * N) zaman mürəkkəbliyinə səbəb olur. Eynilə, bölmə funksiyamız belə zənglər edə bilər. Bunu həll etmək üçün a seçimini təmin edəcəyik təsadüfi bölmənin hər nöqtəsində dönmə.

Alqoritm

  1. Bir yaradın quickSelect () (N - K) -i qaytaran funksiyaən kiçik”Elementi
  2. Bir yaradın bölmə () hər hansı birinin düzgün göstəricisini qaytaracaq köməkçi funksiyası randomly seçilmiş pivot
  3. İndi nöqtəyə çatana qədər bölmə () indeksi 'ilə bərabər qaytarırK':
    • bölməyə () zəng edin təsadüfi mil
    • Döndürülən pivot indeksi ilə eynidir K
      • pivot elementini qaytarın
    • Else qaytarılmış pivot indeksi azdır K
      • arakəsmə () yandır sağ alt massiv pivot indeksinin
    • Else qaytarılmış pivot indeksindən çoxdur K
      • arakəsmə () yandır sol subarray pivot indeksinin
  4. İndi quickSelect () (N - K) indeksini qaytardı, nəticəni yazdırın

Sıralanmamış massivdə Kth ən böyük elementi tapmaq üçün alqoritmin tətbiqi

C ++ Proqramı

#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';
}

Java Proqramı

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

Sıralanmamış bir sıra içərisində Kth ən böyük elementi tapmaq üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

Təkrarlanma əlaqəsi (N = massivin ölçüsü):

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

Təsadüfi seçilmiş bir pivotun dizini iki yarıya böldüyünü gözləyirik. Buna əsasən, mürəkkəbliyi təxminən təxmin etmək olar T (N) = 2N - logN = ~ O (N).

Beləliklə, alqoritm doğrudur. Bununla birlikdə, ən pis vəziyyətdə, seçilən təsadüfi dönərlər massivdə ən böyük / ən kiçik olduqda, Zaman Mürəkkəbliyi olur O (N * N). Ancaq böyük ölçülü bir massivdə bunun baş vermə ehtimalı çox azdır.

Kosmik mürəkkəblik

O (1), yalnız sabit məkandan istifadə edildiyi üçün.

Şərh yaz

Translate »