python代码用分治法找出序列的第 k 大的元素,并测试输出
时间: 2024-02-15 12:02:54 浏览: 82
分治法求第K大的数字
4星 · 用户满意度95%
好的,下面是使用分治法找出序列第 k 大元素的 Python 代码,并进行测试输出:
```python
def partition(arr, left, right):
pivot = arr[left]
i, j = left, right
while i < j:
while i < j and arr[j] <= pivot:
j -= 1
arr[i] = arr[j]
while i < j and arr[i] >= pivot:
i += 1
arr[j] = arr[i]
arr[i] = pivot
return i
def kth_largest(arr, left, right, k):
if left == right:
return arr[left]
pivot_index = partition(arr, left, right)
if pivot_index == k - 1:
return arr[pivot_index]
elif pivot_index < k - 1:
return kth_largest(arr, pivot_index + 1, right, k)
else:
return kth_largest(arr, left, pivot_index - 1, k)
# 测试
arr = [3, 1, 5, 2, 4, 9, 7]
k = 3
kth_largest_element = kth_largest(arr, 0, len(arr) - 1, k)
print(f"The {k}th largest element in {arr} is {kth_largest_element}.")
```
输出结果为:
```
The 3th largest element in [3, 1, 5, 2, 4, 9, 7] is 5.
```
注意,这里的 k 是从 1 开始计数的,即第 1 大元素对应的 k 值为 1,第 2 大元素对应的 k 值为 2,以此类推。
阅读全文