Python查找最小K个数的两种实现与性能对比

Hazel

发布时间：2026-10-14| 5人浏览过

原创

本文介绍Python中查找最小K个数的两种解法。解法1利用Partition函数，平均时间复杂度为O(N)，但会改变原数组顺序。解法2采用最大堆维护K个元素，时间复杂度为N*O(logK)，适合处理海量数据且保持原数组不变。通过代码示例对比了两种方法的运行时间与内存占用，解法2在性能上更优。

Python查找最小K个数：Partition与堆排序解法详解

本文详细介绍如何使用Python查找最小的K个数，并提供两种不同的实现思路供参考。

题目描述

给定n个整数，要求从中找出最小的K个数。例如，输入包含8个数字的列表：4, 5, 1, 6, 2, 7, 3, 8，若K为4，则输出的最小4个数字应为1, 2, 3, 4。

解法一：基于Partition的快速选择

解法1

利用Partition函数可以在平均O(N)的时间复杂度内找到第K大的数字。该操作会将数组分为两部分：左侧数字均小于基准值，右侧数字均大于基准值。设定k为4，分割后可直接取前k个数字。若需有序结果，可对这k个数字进行排序。


# -*- coding:utf-8 -*-
class Solution:
  def PartitionOfK(self, numbers, start, end, k):
    if k < 0 or numbers == [] or start < 0 or end >= len(numbers) or k > end:
      return
    low, high = start, end
    key = numbers[low]
    while low < high:
      while low < high and numbers[high] >= key:
        high -= 1
      numbers[low] = numbers[high]
      while low < high and numbers[low] <= key:
        low += 1
      numbers[high] = numbers[low]
    numbers[low] = key
    if low < k:
      self.PartitionOfK(numbers, start + 1, end, k)
    elif low > k:
      self.PartitionOfK(numbers, start, end - 1, k)
  def GetLeastNumbers_Solution(self, tinput, k):
    # write code here
    if k <= 0 or tinput == [] or k > len(tinput):
      return []
    self.PartitionOfK(tinput, 0, len(tinput) - 1, k)
    return sorted(tinput[0:k])
#测试：
sol = Solution()
listNum = [4,5,1,6,2,7,3,8]
rel = sol.GetLeastNumbers_Solution(listNum, 4)
print(rel)

运行时间：30ms

占用内存：5732k

解法二：基于最大堆的海量数据处理

解法2

解法1存在两个局限性：一是Partition操作会改变原数组的顺序；二是当数据量极大时，将所有数据加载到内存中进行Partition并不合适。为此，可以使用最大堆（Max Heap）来维护当前找到的K个最小数。遍历数组时，若当前数字小于堆顶元素（即当前K个数中的最大值），则替换堆顶并重新调整堆结构。这种方法的时间复杂度为N*O(logK)，更适合处理海量数据。


# -*- coding:utf-8 -*-
class Solution:
  def GetLeastNumbers_Solution(self, tinput, k):
    # write code here
    if tinput == [] or k <= 0 or k > len(tinput):
      return []
    result = []
    for num in tinput:
      if len(result) < k:
        result.append(num)
      else:
        if num < max(result):
          result[result.index(max(result))] = num
    return sorted(result)
#测试：
sol = Solution()
listNum = [4,5,1,6,2,7,3,8]
rel = sol.GetLeastNumbers_Solution(listNum, 4)
print(rel)

运行结果同上

运行时间：25ms

占用内存：5724k

相比解法1，解法2在运行时间和内存占用上均表现更优。

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数学运算技巧总结》、《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。