Leetcode — 215. Kth Largest Element in an Array (中文)

8 min readJan 21, 2021

問題連結: https://leetcode.com/problems/kth-largest-element-in-an-array/

求回傳一個未排序陣列裡面排列由大到小, 第k的數字,
記得我們要的是, 當陣列排序裡面從大的數來第k個數字, 而非所有數字裡第k大的"數字" (也就是若給予陣列有[1,2,2,3] 當k=3的時候, 你須回傳2, 而非1)

範例: 
Input: [3,2,1,5,6,4] and k = 2
Output: 5

想法:

最簡單的方法就是先把陣列由小到大排序, 再回傳裡面排列從後面數回去的第k的數字, 但是我們浪費時間去做我們不需做的事情(也就是排序整個陣列), 代表這方法不會是解這題的最佳解
若我們排序陣列, 若用合併排序法(merge sort)或快速排序(quicksort), 時間複雜度可能就是O(nlogn), 若用氣泡排序(bubble sort)或選擇排序(selection sort)則是O(n²)

那我們就要來想, 我們有沒有辦法在不把整個陣列排序好的情況下, 就找到第k個數字? 有沒有演算法我們可以用來找到現在某個數字在整個陣列中的排名?

如果你很熟悉快速排序, 你可能已經想到可以怎麼做了, 不熟悉quicksort的人也沒關係, 我們都會一步一步做講解我們要怎麼運用演算法來幫忙我們在布排序整個陣列的情況下, 用O(n)的時間來找到陣列中排名第k的數字

程式邏輯:

我們想要用一個partition method可以回傳"基準點(pivot)"的正確所在位置, 同時也會把陣列分成兩部分: 比基準小的在一邊, 比基準大的在另一邊
我們通常當讓 指定的陣列範圍中的最後一個數字當作我們這次partition method裡面的基準點
若你不熟悉在快速排序中的這個partition method也沒關係, 我們在最後會給個例子詳細帶過我們如何實作

在解這題的第一件事情, 就是為了方便我們講解, 我們會把題目一開始給的 "找到排列(由大到小)在第K"的數字, 改成 "找到排列(由小到大)第k"的數字, 也因為我們陣列都是以0開始, 因此我會先把k 轉換成我們要的值, 因此若題目說他想要第1大的數字, 若陣列有10個數字, 我們將k轉換成找到陣列排序後, 位置在9的數字

在主要的程式中,我們做的就是一直呼叫partition method來把陣列分成兩部分並且回傳在範圍中基準點的正確位置, 而當我們說"位置", 我們也可以說程是基準在整個陣列的排名
因此, 我們一知道某數字的排名又外加知道這個數字左側都是小於她的數, 右側都是大於他的數後, 我們又可以把我們尋找排名k的數字的範圍又再次縮小, 若現在拿到的排名比k小, 我們就往左找, 反之亦然!

以下為程式碼運用上述邏輯:

public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        return helper(nums, 0, n-1, n-k);
    }
    public int helper(int[] nums,int s,int e,int k){
        int rank = partition(nums, s, e);
        if(rank==k)
            return nums[rank];
        else if(rank<k)
            return helper(nums, rank+1, e, k);
        else
            return helper(nums, s, rank-1, k);
    }
    public int partition(int[] nums, int s, int e){
        int pivot = nums[e];
        int i = s-1;
        for(int j=s;j<e;j++)
        {
            if(nums[j]>pivot)
                continue;
            swap(nums,++i,j);
        }
        swap(nums,i+1,e);
        return i+1;
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

例子解釋partition method:

我們每次都把在範圍[s, e]中的最後一個數字當作我們這次的基準點
我們在這個方法裡面做的事情就是 一直把比基準點小的數字們調到範圍中的前端部分
所以最終目標就是 找到基準點在這個陣列中的正確位置/真正排名並且又同時把數字們分成比基準小的在範圍內前端, 比基準大的在範圍後端
跑完所有範圍內數字後, 並不保證我們整個陣列都排列好, 我們只是把數字分成兩部分, 以及只能真的幫基準放到正確位置而已

有4個重要的變數需要介紹:

s: 陣列範圍的起始點(我們不在乎位置在s之前的其他數字)
e: 陣列範圍的終點(我們不在乎位置在e之後的其他數字)
j: 一個變數會幫我們走訪從s到e的所有位置, 檢查他們是否大於基準點
i: 一個變數永遠指著我們目前遇到的上一個小於基準點的數字位置, 預設值為s-1, 代表目前還沒有數字比基準小
而在我們走訪完陣列範圍內的數字們後, 我們將會把基準點數字跟(i+1)位置的數字互換, 原因是因為要讓基準點放在比他小的數字位置的正後方

👷舉例來說若我們的陣列長這樣 [2,5,9,1,7,3], 範圍: s = 0, e = 5

🔧Step 0. 初始狀態, i = -1, j = 0

🔧Step 1. j = 0: 我們將會開始來比較現在j指的數字跟基準點的大小
因為arr[0]比基準點小, 我們將會交換arr[i+1]跟arr[j]的位置, 並且把i往後移一位, 因為目前arr[i+1]跟arr[j]指的是同個位置, 實質上我們看不太出來陣列有什麼變化
⚠️我們交換arr[i+1]與arr[j]的數字而非arr[i]與arr[j] 的原因:
因為我們已假設i是指著最近期碰到比基準小的數字, 代表arr[i]的數字已經比基準還小了, 我們不該把他往後放, 因此我們將會換arr[j](比pivot小) 跟 arr[i+1] (比pivot大) 兩數的位置, 讓比基準小的數字往前放