分治法对于给定的n个元素的数组a[1..n],要求从中找出第k小的元素。 【输入样例】 a={20, 43, 32, 67 ,48, 89, 36, 47, 15} k=3 【输出样例】 32
时间: 2024-05-25 16:16:31 浏览: 86
分治算法实验(用分治法查找数组元素的最大值和最小值).docx
5星 · 资源好评率100%
分治法的思路是每次选择一个pivot(可以随机选择),将数组分为两部分:小于pivot的在左边,大于pivot的在右边。然后分别在左右两部分中查找第k小的元素。如果左部分的元素个数小于k,则在右部分中查找第k-leftCount小的元素;如果左部分的元素个数大于等于k,则在左部分中查找第k小的元素。
Python代码如下:
def quickSelect(nums, k):
if not nums:
return None
pivot = nums[0]
leftCount = sum(1 for x in nums if x < pivot)
if leftCount == k - 1:
return pivot
elif leftCount < k - 1:
return quickSelect([x for x in nums if x > pivot], k - leftCount - 1)
else:
return quickSelect([x for x in nums if x < pivot], k)
阅读全文