免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 10083 | 回复: 15

找出数组中第K个小的数---除非你是天才不然就不会写出比我快的了 [复制链接]

论坛徽章:
0
发表于 2003-07-16 21:38 |显示全部楼层
// 找出数组中第K个小的数

//除非你是天才不然就不会写出比我快的了

//最好的算法如下

   

  1. #include <iostream>;
  2. using namespace std;

  3. void swap(int& a, int& b)
  4. {
  5.    int temp = a;
  6.    a = b;
  7.    b = temp;
  8. }   

  9. int k_smallest(int k, int a[], int left, int right)
  10. {
  11.     int pivot = a[right];  //the last item as pivot
  12.     int i = left;
  13.     int j = right-1;
  14.     for(;;)
  15.     {
  16.         for(; a[i]<pivot; i++);
  17.         for(; a[j]>;=pivot; j--);
  18.         if(i<j)
  19.           swap(a[i], a[j]);
  20.         else
  21.           break;   
  22.     }
  23.     swap(a[i], a[right]);
  24.     //now i is the pivot index in the array
  25.     //i.e. a[i] is the (i+1)th smallest item
  26.    
  27.     if(k==i-left+1)
  28.       return a[i];
  29.     else if(k < i-left+1)    //target before pivot
  30.       return k_smallest(k, a, left, i-1);
  31.     else     //target after pivot
  32.       return k_smallest((k-(i-left+1)), a, i+1, right);
  33. }

  34. //find the k_th smallest item in the array
  35. int Kth_smallest(int k, int a[], int size)
  36. {
  37.     return k_smallest(k, a, 0, size-1);
  38. }

  39. int main()
  40. {   
  41.     int a[10] = {4, 8, 1, 5, 2, 9, 3, 7, 10, 6};
  42.    
  43.     for(int i=1; i<=10; i++)
  44.     cout<<Kth_smallest(i, a, 10)<<" ";
  45. }
复制代码

论坛徽章:
0
发表于 2003-07-16 22:48 |显示全部楼层

找出数组中第K个小的数---除非你是天才不然就不会写出比我快的了

假设 m 个数里找出第K个小的数 ,请问你的算法进行多少次比较?

论坛徽章:
0
发表于 2003-07-16 23:09 |显示全部楼层

找出数组中第K个小的数---除非你是天才不然就不会写出比我快的了

不是一个个比较的,

算法和 QUICK SORT 的类似。。

QUICK SORT 是一直在partition array,

这里也是, 先partition array 一次, 看目标在PIVOT前, 还是PIVOT后,   这样一次就能排除了一部分。 再重复以上方法。

论坛徽章:
0
发表于 2003-07-17 00:00 |显示全部楼层

找出数组中第K个小的数---除非你是天才不然就不会写出比我快的了

牛兄:
   我觉得 m 个数里找出第K个小的数 和排序的情况应该有点不同,极端
情况,取第一个,就是 min(m),挨个比较一遍,需要m-1次比较。你那个
算法不知够不够,你可统计打印一下。

论坛徽章:
0
发表于 2003-07-17 00:19 |显示全部楼层

找出数组中第K个小的数---除非你是天才不然就不会写出比我快的了

我觉得可以使用数组的一些特点

如个数是有限的
所以求第K个小的数可以想成N-K个大的数

另外不需要进行排序
只要查找就可以

PS
只是想想
没有认真想

论坛徽章:
0
发表于 2003-07-17 09:55 |显示全部楼层

找出数组中第K个小的数---除非你是天才不然就不会写出比我快的了

最简单、但可能不是最高效的办法:
1。首先对数组进行排序,当然是用最高效的算法
2。根据数组下标找到第k个值
搞定!

论坛徽章:
0
发表于 2003-07-17 11:07 |显示全部楼层

找出数组中第K个小的数---除非你是天才不然就不会写出比我快的了

楼上的,同意是最简单的,但一定不是最高效率的!

论坛徽章:
0
发表于 2003-07-17 12:41 |显示全部楼层

找出数组中第K个小的数---除非你是天才不然就不会写出比我快的了

同意排序来做。
胡哥的算法,看似轻便,其实省去了繁琐的pivot取值。
和quick的缺点一样,当存在极端情况时计算量就变成了O(n^2)。
为了避免该情况,对pivot的要求需要下功夫。
保险起见,常常采用对初值,中值,和末值比较,取出不大不小的。

  1.    int   i , j;
  2.    KEY   pivot;
  3.    
  4.    i = 0;
  5.    j = n-1;
  6.    if ( x[i] >; x[j] ) {
  7.         pivot = x[(i+j)/2] >; x[j] ? x[(i+j)/2] :x[j]
  8.         if ( pivot >; x[i] )
  9.              pivot = x[i];
  10.   }
  11.   else{
  12.         pivot = x[(i+j)/2] >; x[i] ? x[(i+j)/2] :x[i]
  13.         if ( pivot >; x[j] )
  14.              pivot = x[j];
  15.   }


  16.    
  17.    
复制代码


同样需要是经历pivot的选择,不如选择quick排序,然后取出第k个的值。
所以还是排序来的简单。

论坛徽章:
0
发表于 2003-07-17 15:25 |显示全部楼层

找出数组中第K个小的数---除非你是天才不然就不会写出比我快的了

楼主,在抛砖引玉?

论坛徽章:
1
荣誉版主
日期:2011-11-23 16:44:17
发表于 2003-07-17 15:42 |显示全部楼层

找出数组中第K个小的数---除非你是天才不然就不会写出比我快的了

胡青牛,偶支持你一下

继续加油
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP