好资源导航 » 文章资讯 » C++算法之在无序数组中选择第k小个数的实现方法

C++算法之在无序数组中选择第k小个数的实现方法

2024-02-27 08:27:03 209

本文实例讲述了C++算法之在无序数组中选择第k小个数的实现方法。分享给大家供大家参考，具体如下：

从一个无序的整型数组中选出第k小的数，如k=1为最小数，k=n为最大数。这里数组可以是有重复的值！

下面是自己写的一个函数，记在此处来记忆我留下的痕迹！

//选择无序数组中第k小的数
#include
usingnamespacestd;
boolfailed=false;
//这里只考虑数组是int型的
intfindnumber(int*array,intstart,intend,intk)
{
if(array==NULL||start>end||kend+1||k<=0)
{
failed=true;
return0;
}
if(start==end)
{
returnarray[start];
}
intlen=end-start+1;
inttmp=0;
intps=rand()%len+start;
inttk=k;
while(true)
{
//分割两数组
intf=start;
intt=array[ps];
intequalnum=0;
for(inti=start;i<=end;i++)
{
if(array[i]tk&&(f-start+1)==equalnum)
{
returnt;//这里是记录数据相等的数目，当我们从开始start处到最后处end都被这个值给充斥了，那么肯定是这里面的值了，再进行下去就会陷入死循环了。
}
if(tk==(f-start+1))
{
returnt;
}
if((f-start+1)>tk)
{
end=f;
}else
{
start=f+1;
tk=k-start;//这个地方犯过错误，就是写成了k=k-start，在调试的时候老发现无限的循环。后来打印k的值的时候发现k的值都***为负了。这个bug，这个过错使得在一次运行可能会得到正确的数据，但是多次运行后程序就崩溃。
}
len=end-start+1;
ps=rand()%len+start;
}
}
intmain()
{
intarray[10]={1,1,1,2,2,1,4,1,1,1};
for(inti=0;i<10;i++)
{
cout<
先想好，分析好问题，自己脑中构思好了编写的思路，且想好了程序出错的地方再编程，这样会快的很多，而不是一看到问题就框框的在电脑上敲。
希望本文所述对大家C++程序设计有所帮助。

返回顶部
3162201930
czq8825@qq.com

C++算法之在无序数组中选择第k小个数的实现方法

热门推荐

随机推荐