Python实现查找最小的k个数示例【两种解法】

yipeiwu_com7年前Python基础

本文实例讲述了Python实现查找最小的k个数。分享给大家供大家参考,具体如下:

题目描述

输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

解法1

使用partition函数可以知道,使用==O(N)==的时间复杂度就可以找出第K大的数字,并且左边的数字比这个数小,右边的数字比这个数字大。因此可以取k为4,然后输出前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显然是不合适的。因此可以找出结果中最大的数字,如果遍历的数字比这个数字小,则替换,否则不变,可以采用堆的形式来实现数据结构,达到O(logK)的复杂度,因此整体的时间复杂度为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更优。

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

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

相关文章

python yield关键词案例测试

测试环境 win10 python 3.5 yield功能简介 简单来说,yield 的作用就是把一个函数变成一个 generator,带有 yield 的函数不再是一个普通函数,P...

Python中的包和模块实例

一、实例和结果 1)实例的结构和具体的文件: 复制代码 代码如下: PyPackage │  PyCommonM.py │  __init__.py │ ├─p1Pa...

详解Python中的Cookie模块使用

详解Python中的Cookie模块使用

最近在用GAE开发自己的博客程序。虽然GAE的API没有显式的提供操作Cookie的方法,但他现有的架构,使我们有足够的自由来操作Cookie。 Cookie 模块,顾名思义,就是用来操...

Linux下Python安装完成后使用pip命令的详细教程

Linux下Python安装完成后使用pip命令的详细教程

一、很多读者Python安装完成之后,想要下载相关的包,例如:numpy、pandas等Python中这些基础的包,但是,发现pip根本用不了,主要表现在一下几种情况: 二、出现这种情...

详解如何用TensorFlow训练和识别/分类自定义图片

详解如何用TensorFlow训练和识别/分类自定义图片

很多正在入门或刚入门TensorFlow机器学习的同学希望能够通过自己指定图片源对模型进行训练,然后识别和分类自己指定的图片。但是,在TensorFlow官方入门教程中,并无明确给出如何...