|
精华帖 (0) :: 良好帖 (9) :: 新手帖 (15) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-03-31
用大小为100的小顶堆，扫描一遍数字即可，对于每一个数字，与堆顶数比较，如果比堆顶数大，则将堆顶的数修改为较大值，然后重新调整堆（HEAPIFY）。
最后扫描完毕时，堆中的数即TOP100。 时间复杂度O(n),空间为常数（大小为100的堆） |
| 返回顶楼 | |
|
发表时间：2010-03-31
withoutme_hw 写道 用大小为100的小顶堆，扫描一遍数字即可，对于每一个数字，与堆顶数比较，如果比堆顶数大，则将堆顶的数修改为较大值，然后重新调整堆（HEAPIFY）。
最后扫描完毕时，堆中的数即TOP100。 时间复杂度O(n),空间为常数（大小为100的堆） 你这个我也想过 后来算了下 1亿条全部放到堆里做100次heap时间复杂度是O(logn) 比这个方法还是要快很多，不过内存牺牲太多了 具体要看这个题的要求了 |
| 返回顶楼 | |
|
发表时间：2010-03-31
sjynt131 写道 针对这道题优化下算法：
public static int[] findTop100(int[] numbers) {
int[] findNum = new int[100];
int temp = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] > findNum[99]) {
findNum[99] = numbers[i];
}
for (int j = 99; j > 0; j--) {
if (findNum[j] > findNum[j - 1]) {
temp = findNum[j - 1];
findNum[j - 1] = findNum[j];
findNum[j] = temp;
} else {
break;
}
}
}
return findNum;
}
本人机器上1.1秒左右( E2160 * 2G ) 你把findNum作成一个最小堆还能再快点 |
| 返回顶楼 | |
|
发表时间：2010-03-31
感觉前提条件比较模糊，不知是否允许负数，是否允许重复数字 这个对算法应该有影响吧。
|
| 返回顶楼 | |
|
发表时间：2010-03-31
用最大数据的小根堆实现 就行了
|
| 返回顶楼 | |
|
发表时间：2010-03-31
xujunhappy 写道 感觉前提条件比较模糊，不知是否允许负数，是否允许重复数字 这个对算法应该有影响吧。
应该会有负数，重复数吧！ |
| 返回顶楼 | |
|
发表时间：2010-03-31
这种取最大最小数，应该是用红黑树效率最高
大家可以看看红黑树的原理 |
| 返回顶楼 | |
|
发表时间：2010-03-31
没有答案
看你怎么想了 还是分割吧 |
| 返回顶楼 | |
|
发表时间：2010-03-31
这个题目来源于《算法导论》上面，是很经典的问题，答案就是小根堆了。
|
| 返回顶楼 | |
|
发表时间：2010-04-01
堆排序。建立一个100node的堆。
|
| 返回顶楼 | |
