论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2007-09-19 15:18 |只看该作者 |倒序浏览

写一段程序，找出数组中第k大小的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数是7，位置在4。第二大、第三大的数都是4，位置在1、3随便输出哪一个均可。函数接口为：int find_orderk(const int* narry,const int n,const int k)
要求算法复杂度不能是O(n^2）

文库|博客

ypxing

家境小康

论坛徽章:: 0

2楼 [报告]

发表于 2007-09-19 15:28 |只看该作者

1. 利用求中位数的方法求出第k大的数
递归,会用到qsort时用到的partition函数
时间复杂度O(n)
2. 在原数组中查找它的位置
时间复杂度O(n)

[ 本帖最后由 ypxing 于 2007-9-19 15:30 编辑 ]

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

NewCore

家境小康

论坛徽章:: 0

3楼 [报告]

发表于 2007-09-19 15:35 |只看该作者

最屁的数组遍历一遍也就O(n)了，题设的O(n^2)等于没有限制。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

ypxing

家境小康

论坛徽章:: 0

4楼 [报告]

发表于 2007-09-19 15:37 |只看该作者

应该不是吧

原帖由 NewCore 于 2007-9-19 15:35 发表
最屁的数组遍历一遍也就O(n)了，题设的O(n^2)等于没有限制。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

NewCore

家境小康

论坛徽章:: 0

5楼 [报告]

发表于 2007-09-19 15:40 |只看该作者

回复 #4 ypxing 的帖子

不好意思，纠正一下

应该说最坏的情况下的时间复杂度也就O(n^2)

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

1980116

白手起家

论坛徽章:: 0

6楼 [报告]

发表于 2007-09-20 08:35 |只看该作者

回复 #1 1980116 的帖子

高手过来指点一下啊，我感觉这些答案都不合要求

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

ypxing

家境小康

论坛徽章:: 0

7楼 [报告]

发表于 2007-09-20 08:42 |只看该作者

为什么呢?

原帖由 1980116 于 2007-9-20 08:35 发表
高手过来指点一下啊，我感觉这些答案都不合要求

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

aero

版主

论坛徽章:: 1

8楼 [报告]

发表于 2007-09-20 09:19 |只看该作者

怎么的也要排序吧？那个算法三卷本第二卷开始的计数排序应该是LZ需要的。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

dxj_1231 该用户已被删除	9楼 [报告] 发表于 2007-09-20 12:47 \|只看该作者提示: 作者被禁止或删除内容自动屏蔽
dxj_1231 该用户已被删除	实战分享：从技术角度谈机器学习入门\| 【大话IT】RadonDB低门槛向MySQL集群下战书 \| ChinaUnix打赏功能已上线！ \| 新一代分布式关系型数据库RadonDB知多少？