如何使用C++在无序数组中实现选择第k小个数的实现方法
这篇文章给大家分享的是有关如何使用C++在无序数组中实现选择第k小个数的实现方法的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
创新互联建站是一家集网站建设,魏县企业网站建设,魏县品牌网站建设,网站定制,魏县网站建设报价,网络营销,网络优化,魏县网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。
具体如下:
从一个无序的整型数组中选出第k小的数,如k=1为最小数,k=n为最大数。这里数组可以是有重复的值!
下面是自己写的一个函数,记在此处来记忆我留下的痕迹!
//选择无序数组中第k小的数 #includeusing namespace std ; bool failed = false ; //这里只考虑数组是int型的 int findnumber(int *array,int start , int end, int k) { if(array == NULL || start > end || k < start || k > end+1 || k <= 0 ) { failed = true ; return 0; } if(start == end) { return array[start] ; } int len = end - start + 1 ; int tmp = 0 ; int ps = rand()%len +start ; int tk = k ; while(true) { //分割两数组 int f = start ; int t = array[ps] ; int equalnum = 0 ; for(int i = start ; i <= end ; i ++ ) { if(array[i]< t ) { tmp = array[f]; array[f] = array[i]; array[i] = tmp ; f ++ ; }else if(array[i] == t) { tmp = array[f]; array[f] = array[i]; array[i] = tmp ; f ++ ; equalnum ++ ; } } //end f--; if(equalnum > tk && (f - start + 1) == equalnum) { return t ;//这里是记录数据相等的数目,当我们从开始start处到最后处end都被这个值给充斥了,那么肯定是这里面的值了,再进行下去就会陷入死循环了。 } if(tk == (f - start + 1) ) { return t ; } 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 ; } } int main() { int array[10] = {1,1,1,2,2,1,4,1,1,1}; for(int i = 0 ; i < 10 ; i ++ ) { cout< 先想好,分析好问题,自己脑中构思好了编写的思路,且想好了程序出错的地方再编程,这样会快的很多,而不是一看到问题就框框的在电脑上敲。
感谢各位的阅读!关于“如何使用C++在无序数组中实现选择第k小个数的实现方法”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!
本文名称:如何使用C++在无序数组中实现选择第k小个数的实现方法
当前URL:http://scyanting.com/article/ipscee.html