class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
"""堆排序思想"""
def heapify(array, start, end):
while True:
max_pos = start #初始化最大值所在位置為目標所在
if start*2 + 1 <= end and array[max_pos] < array[start*2+1]:
# 如果左葉子節點存在，且大于目標值，則將最大值所在位置指向該節點所在位置
max_pos = start*2 + 1
if start*2 + 2 <= end and array[max_pos] < array[start*2+2]:
# 如果右葉子節點存在，且大于目標值，則將最大值所在位置指向該節點所在位置
max_pos = start*2 + 2
if max_pos == start:
# 如果目標即為最大，完成該節點堆化，跳出回圈
break
# 交換位置，將最大值
array[start], array[max_pos] = array[max_pos], array[start]
start = max_pos
# 建堆,只需要對前半節點堆化
for i in range(len(nums)//2-1, -1, -1):
heapify(nums, i, len(nums)-1)
# 排序，只需要回圈K次，排序TOP K個節點
i = len(nums) - 1
while i > len(nums) - 1 - k:
nums[0], nums[i] = nums[i], nums[0]
i -= 1
heapify(nums, 0, i)
return nums[len(nums)-k]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/135483.html
標籤：其他
上一篇：D. Road to Post Office 決議(思維)
下一篇：反轉鏈表