Python找出最小的K个数实例代码
题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
这个题目完成的思路有很多，很多排序算法都可以完成既定操作，关键是复杂度性的考虑。以下几种思路当是笔者抛砖引玉，如果读者有兴趣可以自己再使用其他方法一一尝试。
思路1：利用冒泡法
临近的数字两两进行比较,按照从小到大的顺序进行交换,如果前面的值比后面的大，则交换顺序。这样一趟过去后,最小的数字被交换到了第一位；然后是次小的交换到了第二位，。。。，依次直到第k个数，停止交换。返回lists的前k个数（lists[0:k]，前闭后开）
思路2：使用快排中的partition思想。
①我们设定partition函数的哨兵为key=lists[left]，在partition函数中完成一轮比较的结果是，比key大的数都在其右边，比key小的数放在其左边。完成该轮后返回其left=right时left的值。
②我们判断left的值是比k大还是小：
如果left的值比k大，说明上轮partition之后，lists中前left个小的数在左边，其余的数在其右边，我们还需要把寻找范围缩小，下次找的时候只在数组前面left个数中找了。
如果left的值比k小，说明上轮partition之后，前left个数找的太少了，我们需要再往数组的后面找。
# -*- coding: utf-8 -*-
"""
Date: Tue Sep 19 10:50:11 2017
Created by @author: xiaoguibao
E-mail: mingliumengshao@163.com
Content: 找最小的k个数
"""
def function1(lists,k):
# 冒泡法
length = len(lists)
for i in range(k):
for j in range(i+1,length):
if lists[i] > lists[j]:
lists[j],lists[i] = lists[i],lists[j]
return lists[0:k]
"""
思路2 包括2个部分function2_partion和function2
"""
def function2_partion(lists,left,right):
#划分函数处理部分
key = lists[left]
while left < right:
while left < right and lists[right] >= key:
right -= 1
lists[left] = lists[right]
while left < right and lists[left] <= key:
left += 1
lists[right] = lists[left]
lists[right] = key
return left
def function2(lists,k):
#划分法主要函数部分
length = len(lists)
left = 0
right = length - 1
index = function2_partion(lists,left,right)
while k!=index:
if index > k-1:
right = index-1
else:
left = index+1
index = function2_partion(lists,left,right)
return lists[0:k]
def main():
lists = [1,1,6,4,11,9,2,10,3]
# print "思路一(冒泡法):",function1(lists,8)
print "思路二(划分法):",function2(lists,8)
if __name__=="__main__":
main()
总结
以上就是本文关于Python找出最小的K个数实例代码的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！
您可能感兴趣的文章:
- python实现决策树分类算法
- Python决策树分类算法学习
- Python数据拟合与广义线性回归算法学习
- Python KNN分类算法学习
- Python文本特征抽取与向量化算法学习
- Python中使用支持向量机(SVM)算法
- 手把手教你python实现SVM算法
- Python实现螺旋矩阵的填充算法示例
相关推荐
-
Python中使用支持向量机(SVM)算法
在机器学习领域,支持向量机SVM(Support Vector Machine)是一个有监督的学习模型,通常用来进行模式识别.分类(异常值检测)以及回归分析. 其具有以下特征: (1)SVM可以表示为凸优化问题,因此可以利用已知的有效算法发现目标函数的全局最小值.而其他分类方法都采用一种基于贪心学习的策略来搜索假设空间,这种方法一般只能获得局部最优解. (2) SVM通过最大化决策边界的边缘来实现控制模型的能力.尽管如此,用户必须提供其他参数,如使用核函数类型和引入松弛变量等. (3)S
-
Python决策树分类算法学习
从这一章开始进入正式的算法学习. 首先我们学习经典而有效的分类算法:决策树分类算法. 1.决策树算法 决策树用树形结构对样本的属性进行分类,是最直观的分类算法,而且也可以用于回归.不过对于一些特殊的逻辑分类会有困难.典型的如异或(XOR)逻辑,决策树并不擅长解决此类问题. 决策树的构建不是唯一的,遗憾的是最优决策树的构建属于NP问题.因此如何构建一棵好的决策树是研究的重点. J. Ross Quinlan在1975提出将信息熵的概念引入决策树的构建,这就是鼎鼎大名的ID3算法.后续的C4.5,
-
Python文本特征抽取与向量化算法学习
本文为大家分享了Python文本特征抽取与向量化的具体代码,供大家参考,具体内容如下 假设我们刚看完诺兰的大片<星际穿越>,设想如何让机器来自动分析各位观众对电影的评价到底是"赞"(positive)还是"踩"(negative)呢? 这类问题就属于情感分析问题.这类问题处理的第一步,就是将文本转换为特征. 因此,这章我们只学习第一步,如何从文本中抽取特征,并将其向量化. 由于中文的处理涉及到分词问题,本文用一个简单的例子来说明如何使用Python的机器
-
Python KNN分类算法学习
本文实例为大家分享了Python KNN分类算法的具体代码,供大家参考,具体内容如下 1.KNN分类算法 KNN分类算法(K-Nearest-Neighbors Classification),又叫K近邻算法,是一个概念极其简单,而分类效果又很优秀的分类算法. 他的核心思想就是,要确定测试样本属于哪一类,就寻找所有训练样本中与该测试样本"距离"最近的前K个样本,然后看这K个样本大部分属于哪一类,那么就认为这个测试样本也属于哪一类.简单的说就是让最相似的K个样本来投票决定. 这里所说的距
-
Python实现螺旋矩阵的填充算法示例
本文实例讲述了Python实现螺旋矩阵的填充算法.分享给大家供大家参考,具体如下: afanty的分析: 关于矩阵(二维数组)填充问题自己动手推推,分析下两个下表的移动规律就很容易咯. 对于螺旋矩阵,不管它是什么鬼,反正就是依次向右.向下.向右.向上移动. 向右移动:横坐标不变,纵坐标加1 向下移动:纵坐标不变,横坐标加1 向右移动:横坐标不变,纵坐标减1 向上移动:纵坐标不变,横坐标减1 代码实现: #coding=utf-8 import numpy ''''' Author: afanty
-
手把手教你python实现SVM算法
什么是机器学习 (Machine Learning) 机器学习是研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能.它是人工智能的核心,是使计算机具有智能的根本途径,其应用遍及人工智能的各个领域. 机器学习的大致分类: 1)分类(模式识别):要求系统依据已知的分类知识对输入的未知模式(该模式的描述)作分析,以确定输入模式的类属,例如手写识别(识别是不是这个数). 2)问题求解:要求对于给定的目标状态,寻找一个将当前状态转换为目标状态的动作序
-
python实现决策树分类算法
本文实例为大家分享了python实现决策树分类算法的具体代码,供大家参考,具体内容如下 1.概述 决策树(decision tree)--是一种被广泛使用的分类算法. 相比贝叶斯算法,决策树的优势在于构造过程不需要任何领域知识或参数设置 在实际应用中,对于探测式的知识发现,决策树更加适用. 2.算法思想 通俗来说,决策树分类的思想类似于找对象.现想象一个女孩的母亲要给这个女孩介绍男朋友,于是有了下面的对话: 女儿:多大年纪了? 母亲:26. 女儿:长的帅不帅? 母亲:挺帅的. 女儿:收入高不?
-
Python数据拟合与广义线性回归算法学习
机器学习中的预测问题通常分为2类:回归与分类. 简单的说回归就是预测数值,而分类是给数据打上标签归类. 本文讲述如何用Python进行基本的数据拟合,以及如何对拟合结果的误差进行分析. 本例中使用一个2次函数加上随机的扰动来生成500个点,然后尝试用1.2.100次方的多项式对该数据进行拟合. 拟合的目的是使得根据训练数据能够拟合出一个多项式函数,这个函数能够很好的拟合现有数据,并且能对未知的数据进行预测. 代码如下: import matplotlib.pyplot as plt import
-
Python找出最小的K个数实例代码
题目描述 输入n个整数,找出其中最小的K个数.例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,. 这个题目完成的思路有很多,很多排序算法都可以完成既定操作,关键是复杂度性的考虑.以下几种思路当是笔者抛砖引玉,如果读者有兴趣可以自己再使用其他方法一一尝试. 思路1:利用冒泡法 临近的数字两两进行比较,按照从小到大的顺序进行交换,如果前面的值比后面的大,则交换顺序.这样一趟过去后,最小的数字被交换到了第一位:然后是次小的交换到了第二位,...,依次直到第k个数,停
-
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 找出list中最大或者最小几个数的索引方法
如下所示: nums = [1,8,2,23,7,-4,18,23,24,37,2] result = map(nums.index, heapq.nlargest(3, nums)) temp=[] Inf = 0 for i in range(3): temp.append(nums.index(max(nums))) nums[nums.index(max(nums))]=Inf result.sort() temp.sort() print(result) print(temp) 如上,
-
Python找出文件中使用率最高的汉字实例详解
本文实例讲述了Python找出文件中使用率最高的汉字的方法.分享给大家供大家参考.具体分析如下: 这是我初学Python时写的,为了简便,我并没在排序完后再去掉非中文字符,稍微会影响性能(大约增加了25%的时间). # -*- coding: gbk -*- import codecs from time import time from operator import itemgetter def top_words(filename, size=10, encoding='gbk'): co
-
python找出一个列表中相同元素的多个索引实例
定义:X=[1,2,3,1,4] 任务:找出元素为1的索引 Solution: # 如果直接用X.index(1),只能得到0这一个索引,而我们需要所有索引. l = len(X) zip_list = zip(*(range(l),X)) id1 = [z[0] for i,z in enumerate(zip_list) if z[1]==1] # 或者更简单的 id1 = [i for i,x in enumerate(X) if x==1] 以上这篇python找出一个列表中相同元素的多
-
Python 找出出现次数超过数组长度一半的元素实例
利用问题的普遍性和特殊性来求解, 代码如下: import unittest from datetime import datetime class GetFreqNumbersFromList(unittest.TestCase): def setUp(self): print("\n") self.start_time = datetime.now() print(f"{self._testMethodName} start: {self.start_time}"
-
Python找出list中最常出现元素的方法
本文实例讲述了Python找出list中最常出现元素的方法.分享给大家供大家参考,具体如下: 假设一个list中保存着各种元素,需要统计每个元素出现的个数,并打印出最常出现的前三个元素分别是什么.list如下: 复制代码 代码如下: word_list =["is","you","are","I","am","OK","is","OK","
-
Java C++题解 leetcode第k个数实例
目录 题目要求 思路一:小根堆 Java C++ 思路二:多路归并[多指针] Java C++ Rust 总结 题目要求 思路一:小根堆 中文题目描述不太清晰,但其实由题目可以发现,当x满足条件时,3x.5x.7x分别也都满足条件. 将满足条件的数依次放入优先队列存放用于后续计算,由于每次要取待计算队列中最小的数x,所以定义小根堆: 弹出x,计算3x.5x.7x并入队: 用一个哈希表记录防止重复入队. 每次取数(pop)时进行计数,到第k次结束,当前队首即为答案. Java <学到了> 1L也
-
用python找出那些被“标记”的照片
源码传送门 环境准备 下面的两个第三方模块都可以直接通过pip快速安装,这里使用py36作为运行环境. python3.6 requests exifread 思路 遍历目录 拉取数据集合 遍历集合取得exif exif信息整理,并获取实体地址 拷贝文件到结果样本目录 生成json报告文件 基础知识 下面是现今相片中会存在与GPS相关的关键字,大牛亦可一比带过~ [参考] { "GPSVersionID": "GPS版本", "GPSLatitudeRef
-
python找出列表中大于某个阈值的数据段示例
该算法实现对列表中大于某个阈值(比如level=5)的连续数据段的提取,具体效果如下: 找出list里面大于5的连续数据段: list = [1,2,3,4,2,3,4,5,6,7,4,6,7,8,5,6,7,3,2,4,4,4,5,3,6,7,8,9,8,6,1] 输出: [[6, 7], [6, 7, 8], [6, 7], [6, 7, 8, 9, 8, 6]] 算法实现: # -*- coding: utf-8 -*- """ --------------------