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

2024/02/13閱讀時間約 8 分鐘


題目敘述

題目會給定一個陣列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還右邊即可)。

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

假如這張牌在整理好之後,落在剛好從左邊數來第三張牌的位置,那麼這張牌就是這副牌中第3大的牌


因此,可以造出一個更高效率,不需要真正去排序整個陣列的演算法。

借用Quick Sort的演算法裡面pivot 和 partition分割的觀念來說,我們可以每回合在區間內隨機選擇一個陣列元素當作pivot,把pivot通過partition分割的操作,放在他對應在陣列中是第j大的位置上,index = j-1


這時候, 每回合判斷當下pivot在partition之後得到的index 是否剛好等於k-1,如果是,那代表這回合被選中的pivot恰好就是就是第k大的元素。
相當於判斷當下的pivot 是否 剛好為第k大的元素。


假如index 還太小,表示第k大的元素落在右邊,下一次迭代收縮窗口,只右邊剩下的區間,再做一次隨機選擇陣列元素做partition(相當於從右邊的區域再抽一張撲克牌做整理)。

假如index 還太大,表示第k大的元素落在左邊,下一次迭代收縮窗口,只搜尋左邊剩下的區間,再做一次隨機選擇陣列元素做partition(相當於從左邊的區域再抽一張撲克牌做整理)。


而且,題目已經保證,k值一定落在合法範圍,所以最後一定找的到答案

程式碼 使用QuickSort的副產品,QuickSelect 快速選擇

class Solution:

def partition(self, nums, left, right):


# Randomized pivot
rnd_idx = random.randint(left, right)
nums[left], nums[rnd_idx] = nums[rnd_idx], nums[left]

pivot = nums[left]
l, r = left+1, right

# Partition based on pivot
while l <= r:

if nums[l] < pivot and nums[r] > pivot:

nums[l], nums[r] = nums[r], nums[l]
l, r = l+1, r-1

if nums[l] >= pivot:
l += 1

if nums[r] <= pivot:
r -= 1


nums[left], nums[r] = nums[r], nums[left]
return r


def findKthLargest(self, nums: List[int], k: int) -> int:

size = len(nums)
left, right = 0, size-1

while left <= right:

cur_index = self.partition( nums, left, right)

if cur_index > k-1:
# miss, current pivot is smaller than k-th largest element
right = cur_index -1

elif cur_index < k - 1:
# miss, currnet pivot is larger than k-th largest element
left = cur_index + 1

else:
# hit, current pivot is k-th largest element
return nums[ cur_index ]

return -1


複雜度分析 使用QuickSort的副產品,QuickSelect 快速選擇

時間複雜度:

Worst case最差情況下,每回合隨機選到的恰好都是最小或最大的牌,這時候會退化成O(n^2)的演算法。

但是Average case平均期望值來說,攤銷分析的時間成本為O(n)。

這邊不延伸展開整個數學證明,有需要的同學可以參考CLSR 演算法楓葉本課本或其他教材關於Randomized QuickSort / QuickSelect的證明。


空間複雜度:

in-place partition,而且我們的實現是迭代版本,所用到的都是固定尺寸的臨時變數,所需空間為O(1) 常數級別。


關鍵知識點

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

聯想到用QuickSelection快速選擇演算法來找出第k大的元素值是誰。


比喻:

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

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

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

假如這張牌在整理好之後,落在剛好從左邊數來第三張牌的位置,那麼這張牌就是這副牌中第3大的牌


Reference:

[1] Kth Largest Element in an Array - LeetCode

29會員
247內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
從 Google News 追蹤更多 vocus 的最新精選內容