數組Leetcode解決方案中的第K個最大元素  


難度級別 中烘焙
經常問 土磚 亞馬遜 蘋果 ByteDance 易趣 Expedia的 Facebook 谷歌 LinkedIn Microsoft微軟 神諭 Salesforce的 Spotify 沃爾瑪實驗室
算法 排列 編碼 分而治之 訪問 面試準備 力碼 力碼解決方案

在此問題中,我們必須在 未分類 排列。 請注意,數組可以有重複項。 因此,我們必須找到 th 按排序順序排列的最大元素,而不是唯一的第K個最大元素。

例  

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

方法(排序數組)  

這種方法很簡單。 對整個數組進行排序。 現在,您可以分辨出數組中任何最大的元素。 但是,足以讓我們找到 th 最大的元素。 這就是為什麼我們可以提出一種更好的方法的原因。

算法

  1. 對數組排序
  2. 從數組後面訪問第K個最大元素
  3. 打印答案

查找未排序數組中第K個最大元素的算法的實現

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

Java程序

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

在未排序數組中找到第K個最大元素的複雜度分析

時間複雜度

O(NlogN),因為我們需要對數組進行排序。 N =數組的大小

也可以看看
路徑穿越Leetcode解決方案

空間複雜度

O(1), 因為我們使用恆定的空間。 備註: 種類() 功能可以使用 上) 記憶。 但這並非總是如此。

方法(快速選擇)  

正如我們在之前的方法中討論的那樣,我們只需要找到 第k個 數組中的最大元素。 以更簡單的方式,我們需要數組中第(n – k + 1)個最小的元素。 說到排序,我們可以想到 快速排序,也有類似的方法。 在快速排序中,選擇一個 樞紐,我們確保它在分區之後到達數組中的正確索引。

如果,我們進行了類似的分區,直到(n – k)索引得到正確的值。 這就是我們將要採用的方法:

未排序數組Leetcode Solutions中的第K個最大元素

選擇一些隨機樞軸並對其周圍的數組進行分區。 如果它達到索引,我們期望(n – k)。 那麼,這是第K個最大元素。 否則,我們知道所需索引位於其左側或右側。 然後,我們可以致電 劃分() 在相應的功能 子陣列 查找所需的索引及其值。

但是,上述方法是否肯定比 排序 一? 我們知道,在這種情況下,當我們選擇最小/最大元素作為關鍵點時,就會發生快速排序的最壞情況,

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

子問題幾乎與問題相同,從而導致O(N * N)時間複雜性。 同樣,我們的分區功能可以進行此類調用。 為了解決這個問題,我們將確保我們選擇一個 隨機 在分區的每個點旋轉。

也可以看看
範圍最大奇數的XOR查詢

算法

  1. 創建一個 quickSelect() 返回第(N – K)個“最少“ 元素
  2. 創建一個 劃分() 輔助函數,它將返回任何正確的索引 隨機 選擇的樞軸
  3. 現在,直到我們到達 劃分() 返回等於'的索引K“:
    • 在一個分區上調用partition() 隨機 樞紐
    • 如果返回的數據透視表索引與 K
      • 返回樞軸元素
    • 否則,如果返回的樞軸索引小於 K
      • 調用partition() 權利 子陣列 樞軸索引的
    • 否則,如果返回的樞軸索引大於 K
      • 調用partition() 左子數組 樞軸索引的
  4. 現在, quickSelect() 返回了第(N – K)個索引,打印結果

查找未排序數組中第K個最大元素的算法的實現

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

Java程序

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

在未排序數組中找到第K個最大元素的複雜度分析

時間複雜度

遞歸關係可以表示為N =數組的大小):

也可以看看
搜尋器日誌文件夾Leetcode解決方案

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

因為我們期望隨機選擇的樞軸將數組分成兩半。 基於此,可以將復雜度粗略估算為 T(N)= 2N – logN =〜O(N)。

因此,該算法是線性的。 但是,在最壞的情況下,當選定的隨機樞軸在數組中都最大/最小時,時間複雜度變為 O(N * N)。 但是在大型陣列中,這種情況發生的可能性很小。

空間複雜度

O(1), 因為只使用恆定的空間。