求最小的k个数[通俗易懂]

求最小的k个数

大家好,又见面了,我是全栈君。

和高速排序有点类似,利用高速排序的划分算法,

划分算法见http://blog.csdn.net/buyingfei8888/article/details/8997803

依据int partition(int number[],int start,int end);返回值为数组下标,大小为index,index左边值均小于number【index】,右边均大于number【index】,若为k-1.则左边值均为所求。

代码:

#include <iostream>

using namespace std;

int partition(int number[],int start,int end){
	int temp=number[start];
	while(start<end){
		while(start<end && number[end]>temp)
			--end;
		if(start < end)
		    number[start++] = number[end];
		while(start<end && number[start]<temp)
			start++;
		if(start<end)
		     number[end--] = number[start];

		number[start]=temp;
	}

	return end;
}

void getLeastNumber(int * input,int start,int end,int * output,int k){
	if(NULL == input || NULL == output || k <=0 || start <0 || end < 1)
		return ;
	int index=partition(input,start,end);
	while(index != k-1){
		if(index > k-1){
			end = index -1;
			index =  partition(input,start,end);
		}
		if(index < k-1){
			start = index + 1;
			index = partition(input , start , end );
		}
	}
	for(int i=0;i<k;i++){
		output[i] = input[i];
		cout<< input[i]<<" ";
	}
	
}


int main(){
	int input[8]={2,1,4,3,99,100,56,909};
	int *output;
	getLeastNumber(input,0,7,output,7);
	return 0;

}

执行结果:

求最小的k个数[通俗易懂]

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115979.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 任务调度器有哪些_本地计算机上的task scheduler

    任务调度器有哪些_本地计算机上的task schedulerTaskScheduler可以看做任务调度的客户端,负责任务的提交,并且请求集群管理器对任务调度。TaskScheduler的类UML图如下,针对不同部署方式会有不同的TaskScheduler与SchedulerBackend进行组合。TaskScheduler类负责任务调度资源的分配,SchedulerBackend负责与Driver、Executor通信收集Executor上分配给该应用的资…

    2022年10月11日
  • flash视频器播放器代码

    flash视频器播放器代码flash视频器播放器代码代码整理:

  • SSM框架下一个简单的模糊查询(超级详细)

    SSM框架下一个简单的模糊查询(超级详细)引言:模糊查询作为后台常用的一种查询方式,我们可以根据相应的关键字对其检索,从而获得所需要的记录,本次模糊查询我们通过名字的任何一个字段进行匹配查询。另外声明,源码就是以下的部分,直接复制就可以使用了。此外,想要模糊查询,最好学会分页查询,分页查询我用了两种方法,一种是利用的pageHelper,另一种没用到插件.需要源码的,或者demo,在我的资源下载,需要远程帮忙的可以加我QQ…

  • TCP和UDP协议的区别_朋友关系

    TCP和UDP协议的区别_朋友关系在解释两者之间的关系之前,我们必须从宏观的角度了解互联网的整个交互模型。因为当了解互联网在大体上是如何运作时,我们才能了解HTTP和TCP存在的意义,包括他们所要解决的问题是。 (此图来自Udacity的网络协议教程)互联网的模型被分为4层,从上至下每一层都依赖其底层协议。换言之,Application(应用层)的协议操作成功的前提是Transport(运输层)的存在。没有运输层就没有应…

  • 回溯法求解N皇后问题及其时间复杂度分析

    回溯法求解N皇后问题及其时间复杂度分析回溯法求解N皇后问题及其时间复杂度分析一、回溯法简介1.什么是回溯法?2.回溯法的时间复杂度分析蒙特卡罗方法蒙特卡罗方法在回溯法求解时间复杂度中的应用二、回溯法求解N皇后问题1.回溯法求解N皇后问题的过程2.回溯法求解N皇后问题的时间复杂度2.1求解时的效率分析回溯法进行效率分析的代码2.2时间复杂度分析一、回溯法简介1.什么是回溯法?  相信”迷宫”是许多人儿时的回忆,大家小时候一定都玩过迷宫游戏。我们从不用别人教导,都知道走迷宫的策略是:当遇到一个岔路口,会有以下两种情况:存

  • 妙用AccessibilityService黑科技实现微信自动加好友拉人进群聊[通俗易懂]

    妙用AccessibilityService黑科技实现微信自动加好友拉人进群聊[通俗易懂]妙用AccessibilityService黑科技实现微信自动加好友拉人进群聊标签:2018引言:在上上周的周六和周日,我发了两篇利用itchat实现微信机器人的文章(Python):小猪的Python学习之旅——18.Python微信转发小宇宙早报小猪的Python学习之旅——19.Python微信自动好友验证,自动回复,发送群聊链接通过把脚本挂到服务器上…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号