題目
給定整數(shù)數(shù)組 nums 和整數(shù) k，請返回數(shù)組中第 k 個最大的元素。請注意，你需要找的是數(shù)組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。
你必須設(shè)計并實現(xiàn)時間復(fù)雜度為 O(n) 的算法解決此問題。
例：
輸入: [3,2,1,5,6,4], k = 2
輸出: 5
方法一：大頂堆、API
- maxheap 建立的頂堆
- 循環(huán)遍歷數(shù)組 nums，將元素的負(fù)值依次放入頂堆。此時，數(shù)組的最大值位于頂堆的頂點，但其值為原值的負(fù)數(shù)，其余同理
- 循環(huán)彈出頂堆的前 k-1 個值，即彈出數(shù)組的前 k-1 個最大值
- 此時頂堆的頂點即為第 k 個最大元素的負(fù)值，返回該值
class Solution(object):
def findKthLargest(self, nums, k):
maxheap = []
for num in nums:
heapq.heappush(maxheap, -num)
for num in range(k-1):
heapq.heappop(maxheap)
return -maxheap[0]
方法二：快速排序
findKthLargest 函數(shù)：尋找數(shù)組中的第 K 個元素
- left 和 right 分別指向數(shù)組的首尾
- 循環(huán)直至輸出第 K 個元素
- index 調(diào)用 partition 函數(shù)獲取本次基準(zhǔn)元素的下標(biāo)
- 判斷基準(zhǔn)元素下標(biāo) index 是否為第 K 個元素，若是則直接返回值
- 若下標(biāo)小于 k-1，即該基準(zhǔn)元素小于第K個最大元素。由于生成的是降序序列，那么此次應(yīng)在該基準(zhǔn)元素的右邊繼續(xù)尋找，所以 left 更新為基準(zhǔn)元素下標(biāo) index 加一
- 若下標(biāo)大于 k-1，即該基準(zhǔn)元素大于第K個最大元素。由于生成的是降序序列，那么此次應(yīng)在該基準(zhǔn)元素的左邊繼續(xù)尋找，所以 right 更新為基準(zhǔn)元素下標(biāo) index 減一
partition 函數(shù)：確定基準(zhǔn)元素處于序列中的位置，最終生成降序序列
- pivot 基準(zhǔn)元素，設(shè)置為該次最左邊的值 nums[left]
- index 下標(biāo)，初始值為 left
- 循環(huán)遍歷 [left+1, right]
- 將大于基準(zhǔn)值的元素放到下標(biāo)較小處，那么小于基準(zhǔn)值的元素被放到下標(biāo)較大處
- 交換基準(zhǔn)值與大于基準(zhǔn)值的最后一個值得位置，使得基準(zhǔn)值處于正確位置
- 返回該基準(zhǔn)值得下標(biāo)
class Solution(object):
def findKthLargest(self, nums, k):
left, right = 0, len(nums)-1
while True:
index = self.partition(nums, left, right)
if index == k-1:
return nums[index]
elif index < k-1:
left = index + 1
else:
right = index - 1
def partition(self, nums, left, right):
pivot = nums[left]
index = left
for i in range(left+1, right+1):
if nums[i] >= pivot:
index += 1
nums[index], nums[i] = nums[i], nums[index]
nums[index], nums[left] = nums[left], nums[index]
return index
例：[3,2,1,5,6,4], k = 2
left = 0，right = 5
index = partition(nums, 0, 5)：
pivot = 3，index = 0
i = 1：nums[1] = 2 < pivot = 3
i = 2：nums[2] = 1 < pivot = 3
i = 3：nums[3] = 5 ≥ pivot = 3 index = 1 nums = [3, 5, 1, 2, 6, 4]
i = 4：nums[4] = 5 ≥ pivot = 3 index = 2 nums = [3, 5, 6, 2, 1, 4]
i = 5：nums[5] = 4 ≥ pivot = 3 index = 3 nums = [3, 5, 6, 4, 1, 2]
nums = [4, 5, 6, 3, 1, 2]
index = partition(nums, 0, 5) = 3
......
相關(guān)知識
堆：
大頂堆： 每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值
小頂堆： 每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值heappush(heap, item)：
heapq.heappush()
向堆中添加新值，建立的是小頂堆?？梢酝ㄟ^添加原值的負(fù)值達(dá)到某種意義上的建立大頂堆，因為此時位于頂點的值雖是添加值得最小值，但是是原值得最大值
heap： 堆
item： 元素heappop(heap)：
heapq.heappop()
從堆中彈出并返回最小值
heap： 堆-
快速排序：
步驟：- 首先設(shè)置一個分界值也就是基準(zhǔn)值又是也稱為監(jiān)視哨，通過該分界值將數(shù)據(jù)分割成兩部分
- 將大于或等于分界值的數(shù)據(jù)集中到右邊，小于分界值的數(shù)據(jù)集中到左邊。一趟排序過后，左邊部分中各個數(shù)據(jù)元素都小于分界值，而右邊部分中各數(shù)據(jù)元素都大于或等于分界值，且右邊部分個數(shù)據(jù)元素皆大于左邊所有數(shù)據(jù)元素
- 然后，左邊和右邊的數(shù)據(jù)可以看成兩組不同的部分，重復(fù)上述1和2步驟
- 當(dāng)左右兩部分都有序時，整個數(shù)據(jù)就完成了排序
參考
代碼相關(guān)：https://leetcode.cn/problems/kth-largest-element-in-an-array/solution/cpython3java-1da-gen-dui-diao-ku-2shou-l-xveq/
堆：https://blog.csdn.net/sinat_34715587/article/details/89195447 https://blog.csdn.net/qq_38022469/article/details/123851001
快速排序：https://blog.csdn.net/qq_52595134/article/details/118943109
