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

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

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

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

//选择无序数组中第k小的数
#include <iostream>
using 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<<findnumber(array,0,9,i+1)<<endl;
  }
  system("pause");
  return 0 ;
}

先想好，分析好问题，自己脑中构思好了编写的思路，且想好了程序出错的地方再编程，这样会快的很多，而不是一看到问题就框框的在电脑上敲。

希望本文所述对大家C++程序设计有所帮助。

# C++ # 算法 # 无序数组 # 选择 # 第k小个数 # C++使用异或运算实现交换两个数的值 # C++如何判断一个数字是否为质数 # C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法 # C++统计中英文大小写字母、数字、空格及其他字符个数的方法 # C++求1到n中1出现的次数以及数的二进制表示中1的个数 # c++统计文件中字符个数代码汇总 # c++通过引用实现三个数字求最大值 # 利用C++的基本算法实现十个数排序 # 用C++实现求N!中末尾0的个数的方法详解 # 组中 # 想好 # 就会 # 好了 # 是有 # 给大家 # 当我们 # 脑中 # 这里面 # 所述 # 程序设计 # 而不是 # 整型 # 写成了 # 一个函数 # 讲述了 # lt # iostream # js # include

返回目录在线咨询

上一篇：如何优化域控站点间的复制流量以提高性能？
下一篇：php数组下标从0开始修改_php调整数组起始索引技巧【教程】

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

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

您的项目需求