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

本文实例讲述了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程序设计有所帮助。

赞 (0)

相关推荐

  • python二分查找算法的递归实现方法

    本文实例讲述了python二分查找算法的递归实现方法.分享给大家供大家参考,具体如下: 这里先提供一段二分查找的代码: def binarySearch(alist, item): first = 0 last = len(alist)-1 found = False while first<=last and not found: midpoint = (first + last)//2 if alist[midpoint] == item: found = True else: if ite

  • Python中的二叉树查找算法模块使用指南

    python中的二叉树模块内容: BinaryTree:非平衡二叉树  AVLTree:平衡的AVL树  RBTree:平衡的红黑树 以上是用python写的,相面的模块是用c写的,并且可以做为Cython的包. FastBinaryTree  FastAVLTree  FastRBTree 特别需要说明的是:树往往要比python内置的dict类慢一些,但是它中的所有数据都是按照某个关键词进行排序的,故在某些情况下是必须使用的. 安装和使用 安装方法 安装环境: ubuntu12.04, py

  • Python cookbook（数据结构与算法）找到最大或最小的N个元素实现方法示例

    本文实例讲述了python找到最大或最小的N个元素实现方法.分享给大家供大家参考,具体如下: 问题:想在某个集合中找出最大或最小的N个元素 解决方案:heapq模块中的nlargest()和nsmallest()两个函数正是我们需要的. >>> import heapq >>> nums=[1,8,2,23,7,-4,18,23,42,37,2] >>> print(heapq.nlargest(3,nums)) [42, 37, 23] >&g

  • Python查找两个有序列表中位数的方法【基于归并算法】

    Python查找两个有序列表中位数的方法【基于归并算法】

    本文实例讲述了Python查找两个有序列表中位数的方法.分享给大家供大家参考,具体如下: 今天做到的一个机试题目,很简单,这里简单记录一下: 我用的是归并的思想,当然还可以用递归的方法,下面是具体实现: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:找到两个有序列表的中位数 若列表总长度为奇数则直接返回中间下标的值 否则返回前一个值,如长度为6则返回下标为2处的值 ''' import random def rando

  • Python有序查找算法之二分法实例分析

    本文实例讲述了Python有序查找算法之二分法.分享给大家供大家参考,具体如下: 二分法是一种快速查找的方法,时间复杂度低,逻辑简单易懂,总的来说就是不断的除以2除以2... 例如需要查找有序数组arr里面的某个关键字key的位置,那么首先确认arr的中位数或者中点center,下面分为三种情况: ① 假如arr[center]>key,说明key在arr中心左边范围: ② 假如arr[center]<key,说明key在arr中心右边范围: ③ 假如arr[center]=key,说明key

  • Python实现二分查找算法实例

    本文实例讲述了Python实现二分查找算法的方法.分享给大家供大家参考.具体实现方法如下: #!/usr/bin/env python import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval < m: low = mid + 1 elif midval > m: high = mid - 1 else:

  • Python使用min、max函数查找二维数据矩阵中最小、最大值的方法

    本文实例讲述了Python使用min.max函数查找二维数据矩阵中最小.最大值的方法.分享给大家供大家参考,具体如下: 简单使用min.max函数来得到二维数据矩阵中的最大最小值,很简单,这是因为工作需要用到一个东西所以先简单来写了一下: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:找出来随机生成矩阵中的最大.最小值 ''' import time import random def random_matrix_ge

  • python快速查找算法应用实例

    本文实例讲述了Python快速查找算法的应用,分享给大家供大家参考. 具体实现方法如下: import random def partition(list_object,start,end): random_choice = start #random.choice(range(start,end+1)) #把这里的start改成random()效率会更高些 x = list_object[random_choice] i = start j = end while True: while li

  • Python实现在某个数组中查找一个值的算法示例

    第一种算法思路: 第一步:随机出来一个数组的下标 第二步:判断下标对应的值是否等于被查找的值,是的话终止,已找到,否的话转第三步. 第三步:判断是否随机完数组的所有下标,是的话终止,没找到,否的话转第一步. 代码如下: #本程序的功能是在字典中查找存在某个值 import random di = {'a':1,'b':2,'c':3,'d':4,'e':5,'f':6} key = 2 di1 = {} while True: tmp = random.choice(di.keys()) #随机

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

    本文实例讲述了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 So

  • Python找出最小的K个数实例代码

    题目描述 输入n个整数,找出其中最小的K个数.例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,. 这个题目完成的思路有很多,很多排序算法都可以完成既定操作,关键是复杂度性的考虑.以下几种思路当是笔者抛砖引玉,如果读者有兴趣可以自己再使用其他方法一一尝试. 思路1:利用冒泡法 临近的数字两两进行比较,按照从小到大的顺序进行交换,如果前面的值比后面的大,则交换顺序.这样一趟过去后,最小的数字被交换到了第一位:然后是次小的交换到了第二位,...,依次直到第k个数,停

  • python爬虫 使用真实浏览器打开网页的两种方法总结

    1.使用系统自带库 os 这种方法的优点是,任何浏览器都能够使用, 缺点不能自如的打开一个又一个的网页 import os os.system('"C:/Program Files/Internet Explorer/iexplore.exe" http://www.baidu.com') 2.使用python 集成的库 webbroswer python的webbrowser模块支持对浏览器进行一些操作,主要有以下三个方法: import webbrowser webbrowser.

  • python批量生成身份证号到Excel的两种方法实例

    python批量生成身份证号到Excel的两种方法实例

    身份证号码的编排规则 前1.2位数字表示:所在省份的代码: 第3.4位数字表示:所在城市的代码: 第5.6位数字表示:所在区县的代码: 第7~14位数字表示:出生年.月.日: 第15.16位数字表示:所在地的派出所的代码: 第17位数字表示性别:奇数表示男性,偶数表示女性: 第18位数字是校检码,计算方法如下: (1)将前面的身份证号码17位数分别乘以不同的系数.从第一位到第十七位的系数分别为:7-9-10-5-8-4-2-1-6-3-7-9-10-5-8-4-2. (2)将这17位数字和系数相

  • 对python捕获ctrl+c手工中断程序的两种方法详解

    日常编写调试运行程序过程中,难免需要手动停止,以下两种方法可以捕获ctrl+c立即停止程序 1.使用python的异常KeyboardInterrupt try: while 1: pass except KeyboardInterrupt: pass 2.使用signal模块 def exit(signum, frame): print('You choose to stop me.') exit() signal.signal(signal.SIGINT, exit) signal.sign

  • python 将对象设置为可迭代的两种实现方法

    1.实现 __getitem__(self) class Library(object): def __init__(self): self.value=['a','b','c','d','e'] def __getitem__(self, i): if i>=len(self.value): raise IndexError("out of index") value=self.value[i] return value 调用的时候,系统默认从0 开始传入,并使得i=i+1 2

  • python获得命令行输入的参数的两种方式

    外部直接执行python文件时,我们有时需要获得命令行的参数 获得命令行参数的两种方式 1.通过sys.argv sys.argv:获得一个参数列表,第一个值为文件名本身,通过sys.argv[1]获得第文件名后的第一个参数 ,多个参数使用空格隔开 测试代码: import sys print(sys.argv) print(len(sys.argv)) print(len(sys.argv[1])) 测试数据: python3 test.py 第一个参数 第二个参数 执行结果: ['test.

  • python学习之第三方包安装方法（两种方法）

    python学习之第三方包安装方法（两种方法）

    这篇文章主要介绍了python学习之第三方包安装方法,最近在学习QQ空间.微博(爬虫)模拟登录,都涉及到了RSA算法.这样需要下一个RSA包(第三方包),在网上搜了好多资料,具体有以下两种方法: 第一种方法(不使用pip或者easy_install): Step1:在网上找到的需要的包,下载下来.eg. rsa-3.1.4.tar.gz Step2:解压缩该文件. Step3:命令行工具cd切换到所要安装的包的目录,找到setup.py文件,然后输入python setup.py install

  • 详解使用python的logging模块在stdout输出的两种方法

    详解使用python的logging模块在stdout输出 前言: 使用python的logging模块时,除了想将日志记录在文件中外,还希望在前台执行python脚本时,可以将日志直接输出到标准输出std.out中. 实现 logging模块可以有两种方法实现该功能: 方案一:basicconfig import sys import logging logging.basicConfig(stream=sys.stdout, level=logging.DEBUG) 方案二:handler

  • 把JSON数据格式转换为Python的类对象方法详解（两种方法）

    JOSN字符串转换为自定义类实例对象 有时候我们有这种需求就是把一个JSON字符串转换为一个具体的Python类的实例,比如你接收到这样一个JSON字符串如下: {"Name": "Tom", "Sex": "Male", "BloodType": "A", "Hobbies": ["篮球", "足球"]} 我需要把这个转换为具

随机推荐