一聚教程网:一个值得你收藏的教程网站

热门教程

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

时间:2022-06-25 04:36:40 编辑:袖梨 来源:一聚教程网

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

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

 

 代码如下复制代码

//选择无序数组中第k小的数

#include

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;

    return0;

  }

  if(start == end)

  {

    returnarray[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 ++ ;

        }elseif(array[i] == t)

        {

          tmp = array[f];

          array[f] = array[i];

          array[i] = tmp ;

          f ++ ;

          equalnum ++ ;

        }

    }//end

    f--;

    if(equalnum > 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 ;

  }

}

int main()

{

  int array[10] = {1,1,1,2,2,1,4,1,1,1};

  for(int i = 0 ; i < 10 ; i ++ )

  {

    cout<

  }

  system("pause");

  return0 ;

}

 

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

热门栏目