pythonでleetcodeでk番目に大きい数を取得する方法

クイックセレクトアルゴリズムを用いて、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です。