69,377
社区成员
发帖
与我相关
我的任务
分享请发表友善的回复…
发表回复
CodeSpy 2009-07-31
- 打赏
- 举报
建立一个大顶堆，堆元素个数上限为5。将数据逐个放入堆中直到堆中的元素个数达到5个的时候，之后取余下的新据与堆顶的元素进行比较。如果新取的数据小于堆顶的元素，那么就删除堆顶，将新数据放入堆中。。。
pigniyan 2009-07-31
- 打赏
- 举报
对数组进行排序,然后输出前5个数,这是最简洁的办法了
BuleRiver 2009-07-30
- 打赏
- 举报
用线形查找算法找第5小的数，复杂度为O(n),然后从中找到比它小的4个数。
黄舒颖 咸丫蛋 2009-07-30
- 打赏
- 举报
同意这个方法。
有一个改进就是比较的时候可以二分比较。
先比较最后一个
再比较中间一个，
还有3楼所说用快分法的改进也OK
三[Quote=引用 9 楼 lijian22500 的回复:]
声明一个5元素的数组，并赋上最大值，然后循环取条件数组中的数，将此数与你声明的数组中的第5个元素进行比较，比它小，就跟第4个元素比较，还比它小，就跟第3个进行比较，如果比它大。那就4元素后移，你所取的数插入原来4元素所在的位置，同理取条件数组中的下一个元素，同上做一样处理。
建议，可以声明一个5元素的链表，指针操作，比5元素的数组后移效率要高。
[/Quote]
有一个改进就是比较的时候可以二分比较。
先比较最后一个
再比较中间一个，
还有3楼所说用快分法的改进也OK
三[Quote=引用 9 楼 lijian22500 的回复:]
声明一个5元素的数组，并赋上最大值，然后循环取条件数组中的数，将此数与你声明的数组中的第5个元素进行比较，比它小，就跟第4个元素比较，还比它小，就跟第3个进行比较，如果比它大。那就4元素后移，你所取的数插入原来4元素所在的位置，同理取条件数组中的下一个元素，同上做一样处理。
建议，可以声明一个5元素的链表，指针操作，比5元素的数组后移效率要高。
[/Quote]
mstlq 2009-07-30
- 打赏
- 举报
直接使用STL中的std::nth_element就可以了^_^
zbihong 2009-07-30
- 打赏
- 举报
如果1亿个数就麻烦了！
lijian22500 2009-07-30
- 打赏
- 举报
声明一个5元素的数组，并赋上最大值，然后循环取条件数组中的数，将此数与你声明的数组中的第5个元素进行比较，比它小，就跟第4个元素比较，还比它小，就跟第3个进行比较，如果比它大。那就4元素后移，你所取的数插入原来4元素所在的位置，同理取条件数组中的下一个元素，同上做一样处理。
建议，可以声明一个5元素的链表，指针操作，比5元素的数组后移效率要高。
建议，可以声明一个5元素的链表，指针操作，比5元素的数组后移效率要高。
liao05050075 2009-07-30
- 打赏
- 举报
呵呵。5次遍历数组也行吧。复杂度同样是O(n)
beyondjdg 2009-07-30
- 打赏
- 举报
[Quote=引用 3 楼 liuxinkun 的回复:]
找第n小元，记得用快速排序法改改就可以出来，但不用排出来。
[/Quote]
这个好像是最好的方法……
找第n小元，记得用快速排序法改改就可以出来，但不用排出来。
[/Quote]
这个好像是最好的方法……
晨星 2009-07-30
- 打赏
- 举报
直接使用STL中的std::nth_element，应该就可以。
fallening 2009-07-30
- 打赏
- 举报
或者自己写一个：
1 void swap( int& a, int& b )
2 {
3
4 a ^= b;
5 b ^= a;
6 a ^= b;
7 }
8
9 int partation( int* arr, int low, int high )
10 {
11 int ans = low - 1;
12 for ( int i = low; i < high; ++i )
13 {
14 if ( arr[i] < arr[high] )
15 {
16 swap( arr[i], arr[++ans] );
17 }
18 }
19 swap( arr[++ans], arr[high] );
20 return ans;
21 }
22
23 int nth( int* arr, int low, int high, int index )
24 {
25 int mid = partation(arr, low, high);
26 if ( mid == index ) return arr[mid];
27 return
28 ( mid < index ) ?
29 nth(arr, mid+1, high, index) :
30 nth(arr, low, mid-1, index);
31 }fallening 2009-07-30
- 打赏
- 举报
这样，直接使用库函数，复杂度是O(n)
int arr[10000];
......
nth_element( arr, arr+5, arr+10000);LIUXINKUN 2009-07-30
- 打赏
- 举报
找第n小元，记得用快速排序法改改就可以出来，但不用排出来。
emyueguang 2009-07-30
- 打赏
- 举报
两重循环，依次找出第一小，第二小，。。。，这样的话不必将所有的元素排过序之后再来看哪个是最小的
ljt3969636 2009-07-30
- 打赏
- 举报
用库函数排序后输出5个已经是很傻瓜且捷径的办法了...
