隨機快速選擇: 陣列中第k大的元素 Kth Largest Element in Array_Leetcode #215

Klim Musalimov on Unsplash

題目敘述

題目會給定一個陣列nums 和 給定的k值，要求我們找出陣列裡第k大的元素。

題目的原文敘述

測試範例

Example 1:

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

第二大的元素為5​

Example 2:

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

第四大的元素為4​

約束條件

Constraints:

• 1 <= k <= nums.length <= 10^5

k 值介於1 ~ 陣列長度之間。

陣列長度介於1 ~ 10^5 之間，而且一定大於等於k。

• -10^4 <= nums[i] <= 10^4

陣列內的每個元素一定介於 負一萬~正一萬 之間。

演算法 使用QuickSort的副產品，QuickSelect 快速選擇

第一直覺的寫法通常是先排序好所有陣列元素，再取出對應第k大的元素，返回答案。

從大到小排列的話，第k大的元素會恰好落在nums[k-1]這個位置上。

但是，深入思考之後，其實可以發現，我們真正要的是第k大的元素值，並不需要知道其他每一個更小或更大的值是誰。

比喻:

好比說我們拿到一副打散的牌，想知道這副牌中第3大的牌是哪一張，那麼我們每回合可以隨機選一張，把這張牌(相當於pivot)放到手牌中對應的位置。

把所有比這張牌還小的都丟到右邊(具體哪個位置無所謂，只要落在剛剛選的那張pivot還右邊即可)。