[LeetCode] 215. Kth Largest Element in an Array

前言

　　解這題最重要的是學習 Quick Sort 快速排序演算法是如何運作的，實作中間也可學到遞迴的概念，題目目標是把陣列從小到大排序後，找到給定的元素大小位置就是答案，在每次遞歸中我們需要線性的時間 O(n) 來進行分區操作。快速排序的遞歸樹的深度為 O(log n)，時間複雜度估算為 O(n log n)，這裡有 JAVA 和 Python 的寫法。

題目

Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?

給定一個整數陣列 nums 和一個整數 k，回傳在這個陣列裡第 k 個最大的元素
注意它是排序順序中第 k 個最大的元素，不是第 k 個不同的元素
你能不排序解決它嗎?

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

題目限制

1 <= k <= nums.length <= 105
104 <= nums[i] <= 104

範例

1 2	Input: nums = [3,2,1,5,6,4], k = 2 Output: 5

1 2	Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4

思路&筆記

解這題之前可能要先去了解一下 Quick Sort 快速排序演算法的原理，來作這題會比較好懂
不過也是可以使用語言自帶的 sort() 方法來排序完，之後再把 k 個索引減掉就是答案了
另外這題也有運用到遞迴的概念，可能也要稍微去了解一下
這題總共會寫到三個 function，第一個 quickSort() 來執行遞迴，第二個 partition() 來執行把陣列排序後找到某個元素最正確的位置，第三個 swap() 來執行元素和元素間的交換

原本的 function 來呼叫自己寫的 quickSort() ，把陣列元素從小排到大，之後陣列的長度減掉 k 個索引就是我們要的答案

執行 quickSort() ，呼叫第一次 partition() 方法會取得 pivot 的最正確的位置 ( pivot 作為中心點用於分辨左右兩邊的元素)

之後利用遞迴重複做 partition() 方法裡面的事情，partition() 方法已經做完一次排序了但還不夠完整，需要靠多次遞迴做一樣的事把小到大排序排到完整，做完第一次會把較小的元素放在 pivot 的左邊，右邊都放較大的元素，這裡會呼應上面所講的 pivot 的位置很重要，後續做的遞迴都是依靠這個位置在分辨左右邊的元素 (下方有示意圖可供參考)

不過做遞迴時傳進去的參數是 quickSort(nums, start, pivot - 1); 和 quickSort(nums, pivot + 1, end);，最後會得出整個陣列以小到大的排序結果

另外也寫了 swap() 方法，用於交換元素

[備註] pivot - 1 的意思是，partition() 做第一次排序的時候 pivot 最正確的位置已經被找出來了，遞迴在往後做的時候僅只要做左半邊的部分，所以迴圈的結束點會落在 pivot 的前一個索引，右半邊原理相同，起始點從 pivot +1 開始做循環。

partition function 示意圖

// 陣列範例 [5, 7, 1, 3, 2, 4]
int pivot = end;                     // pivot 比較的目標數 (指標二)
int pivotIndex = start;              // pivotIndex 最正確的位置 (指標三)
for(int i = start; i < end; i++){    // i 迴圈起始 指標一
}

     i                           pivot
     ↓                             ↓
[    5,    7,    1,    3,    2,    4    ]
     ↑
 pivotIndex

num[i] > num[pivot] 不做交換

           i                     pivot
           ↓                       ↓
[    5,    7,    1,    3,    2,    4    ]
     ↑
 pivotIndex

num[i] > num[pivot] 不做交換

                 i               pivot
                 ↓                 ↓
[    5,    7,    1,    3,    2,    4    ]
     ↑
 pivotIndex

num[i] < num[pivot]
num[i] 和 num[pivotIndex] 做交換
(1 跑到 5 的位置)
pivotIndex++

                       i         pivot
                       ↓           ↓
[    1,    7,    5,    3,    2,    4    ]
           ↑
       pivotIndex

num[i] < num[pivot]
num[i] 和 num[pivotIndex] 做交換
(3 跑到 7 的位置)
pivotIndex++

                             i   pivot
                             ↓     ↓
[    1,    3,    5,    7,    2,    4    ]
                 ↑
             pivotIndex

num[i] < num[pivot]
num[i] 和 num[pivotIndex] 做交換
(2 跑到 5 的位置)
pivotIndex++

                                i、pivot
                                  ↓↓
[    1,    3,    2,    7,    5,    4    ]
                       ↑
                   pivotIndex

i = end 所以 for 迴圈停止
pivotIndex 和 i 做交換

[    1,    3,    2,    4,    5,    7    ]
                       ↑
                   pivotIndex
陣列已排序了第一次
把 pivotIndex 回傳出去

JAVA 實現

class Solution {
    public int findKthLargest(int[] nums, int k) {
        quickSort(nums, 0, nums.length - 1);
        return nums[nums.length - k]; // 已排序後的陣列(小到大)，減掉 k 個索引
    }
    
    private void quickSort(int[] nums, int start, int end){
        // 從陣列的第一個元素做到倒數第二個元素
        if (start < end) {
            int pivot = partition(nums, start, end); // 找出最正確的位置
            // 做遞迴
            // pivot-1 代表循環左半邊元素時，start 指標從索引 0 開始循環，循環到 pivot 前一個索引結束
            // pivot+1 代表循環右半邊元素時， start 指標從 pivot 的後面一個索引開始循環，到最後一個索引結束
            quickSort(nums, start, pivot - 1); 
            quickSort(nums, pivot + 1, end); 
        }
    }

    // 先執行一次，把最後一個元素放到最正確的位置上
    private int partition(int[] nums, int start, int end){

        int pivot = end; // 陣列裡最後一個索引 (指標二)
        int pivotIndex = start; // 陣列裡第一個索引 (指標三)

        // i (指標一)
        for(int i = start; i < end; i++){
            // 開始從前面遍歷陣列，把每個元素和最後一個元素比較
            if(nums[i] < nums[pivot]){
                swap(nums, i, pivotIndex); // 指標一、指標三做交換
                pivotIndex++; 
            }
        }

        // 元素全部做完，最後要把 pivot 放到最正確的位置上
        swap(nums, pivotIndex, pivot);
        return pivotIndex; 
    }

    // 交換函數
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Python 實現

使用了和 Java 一樣的邏輯執行，換成 Python 的寫法。

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        self.quickSort(nums, 0, len(nums) - 1)
        return nums[len(nums) - k]  # 已排序後的陣列(大到小)，取倒數第 k 個元素

    def quickSort(self, nums: List[int], start:int, end:int) -> int:
        if start < end:
            pivot = self.partition(nums, start, end)  # 第一次排序得到 pivot 最正確的位置
            self.quickSort(nums, start, pivot - 1)  # 處理左邊
            self.quickSort(nums, pivot + 1, end)  # 處理右邊

    def partition(self, nums: List[int], start:int, end:int) -> int:

        pivot = end  # 指標二
        pivotIndex = start  # 指標三

        # i 為指標一
        for i in range(start, end):
            # 把每個元素和最後一個元素比較
            if nums[i] < nums[pivot]:
                self.swap(nums, i, pivotIndex)  # 交換
                pivotIndex += 1
        self.swap(nums, pivot, pivotIndex)  # 把 pivot 放到最正確的位置上
        return pivotIndex

    # 交換函數
    def swap(self, nums: List[int], i:int, j:int) -> int:
        temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp

成績

Language	Runtime	Memory
Java	138ms	54.27MB
Python	9610ms	32.34MB

參考資料

Quick Sort 快速排序：https://www.youtube.com/watch?v=mrW5OSr3OVc