Python实现查找最小的k个数

您好，关于Python实现查找最小的k个数，我可以提供以下两种常见的方法：

方法一：使用堆

将数组前k个元素建立小根堆，然后遍历剩余元素，若比堆顶元素小，则将其加入堆中，同时将堆顶元素删除，最终堆中的k个元素即为所求。具体代码如下：

import heapq

def find_k_min(nums, k):
if not nums or k <= 0 or k > len(nums):
return None
res = []
for i in range(k):
heapq.heappush(res, nums[i])
for i in range(k, len(nums)):
if nums[i] < res[0]:
heapq.heappop(res)
heapq.heappush(res, nums[i])
return res

方法二：使用快排的思想

使用快排的思想，每次选择一个基准元素，将小于基准元素的放在左边，大于等于基准元素的放在右边，然后判断基准元素的位置，若该位置等于k-1，则基准元素以及左边的元素就是所求；若该位置小于k-1，则在右半边继续查找；若该位置大于k-1，则在左半边继续查找。具体代码如下：

def find_k_min(nums, k):
if not nums or k <= 0 or k > len(nums):
return None
left, right = 0, len(nums)-1
while True:
index = partition(nums, left, right)
if index == k-1:
return nums[:k]
elif index < k-1:
left = index + 1
else:
right = index - 1

def partition(nums, left, right):
pivot = nums[left]
while left < right:
while left < right and nums[right] >= pivot:
right -= 1
nums[left] = nums[right]
while left < right and nums[left] < pivot:
left += 1
nums[right] = nums[left]
nums[left] = pivot
return left

希望能对您有所帮助！