python

python怎么实现leetcode求第k大的数

小亿
131
2023-10-16 10:17:46
栏目: 编程语言

可以使用快速选择算法来实现求第k大的数。快速选择算法的思想是基于快速排序,通过每次将数组划分为两个部分,将选定的元素放在正确的位置上,从而找到第k大的数。

下面是使用快速选择算法实现求第k大的数的Python代码:

def partition(nums, left, right):
pivot = nums[left]
i = left + 1
j = right
while True:
while i <= j and nums[i] >= pivot:
i += 1
while i <= j and nums[j] <= pivot:
j -= 1
if i <= j:
nums[i], nums[j] = nums[j], nums[i]
else:
break
nums[left], nums[j] = nums[j], nums[left]
return j
def findKthLargest(nums, k):
left = 0
right = len(nums) - 1
while True:
pos = partition(nums, left, right)
if pos == k - 1:
return nums[pos]
elif pos > k - 1:
right = pos - 1
else:
left = pos + 1

使用示例:

nums = [3, 2, 1, 5, 6, 4]
k = 2
result = findKthLargest(nums, k)
print(result)  # 输出: 5

在以上示例中,我们给定了一个数组nums和一个整数k,然后调用findKthLargest函数来求第k大的数。输出结果为5,表示数组nums中第2大的数为5。

0
看了该问题的人还看了