|
精华帖 (0) :: 良好帖 (9) :: 新手帖 (15) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-04-01
推快速排序
|
| 返回顶楼 | |
|
发表时间：2010-04-01
推快速排序
|
| 返回顶楼 | |
|
发表时间：2010-04-01
推快速排序，可以先忽略一亿，按常规做法后，在考虑大数的情况
|
| 返回顶楼 | |
|
发表时间：2010-04-01
最后修改：2010-04-01
恩，1000W，不算数据初始化时间，62ms.
1Y,672ms |
| 返回顶楼 | |
|
发表时间：2010-04-01
import java.util.Comparator;
import java.util.Random;
import java.util.TreeSet;
public class test {
/**
* @param args
*/
public static void main(String[] args) {
final int count = 100000000;
final Random r = new Random();
TreeSet<Integer> data = new TreeSet<Integer>(new Comparator<Integer>() {
public int compare(Integer i, Integer j) {
return j - i;
}
});
for (int i = 0; i < count; i++) {
data.add(r.nextInt());
while (data.size() > 100) {
data.remove(data.last());
}
}
for (int num : data) {
System.out.println(num);
}
}
}
|
| 返回顶楼 | |
|
发表时间：2010-04-01
我们想一起去了，不过你的太复杂了哦：下面看我的罗
thorlst 写道
import java.util.Comparator;
import java.util.Random;
import java.util.TreeSet;
public class test {
/**
* @param args
*/
public static void main(String[] args) {
final int count = 100000000;
final Random r = new Random();
TreeSet<Integer> data = new TreeSet<Integer>(new Comparator<Integer>() {
public int compare(Integer i, Integer j) {
return j - i;
}
});
for (int i = 0; i < count; i++) {
data.add(r.nextInt());
while (data.size() > 100) {
data.remove(data.last());
}
}
for (int num : data) {
System.out.println(num);
}
}
}
我的运行样本为100000000 耗时:15.223s
/**
* @jdk 1.6
* @author skzr.org(E-mail:skzr.org@gmail.com)
* @version 1.0.0
*/
public class Top<T> {
private final TreeSet<T> buf = new TreeSet<T>();
private final int max;
public Top(int max) {
this.max = max < 0 ? 0 : max;
}
public void add(T v) {
if (max != 0) {
buf.add(v);
if (buf.size() > max) buf.pollFirst();
}
}
public SortedSet<T> getSet() {
return buf;
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
Top<Integer> top = new Top<Integer>(200);
for (int i = 0; i < 100000000; i++) {
top.add(i);
}
System.out.println("耗时:" + ((System.currentTimeMillis() - start)/1000d) + "s");
}
}
|
| 返回顶楼 | |
|
发表时间：2010-04-01
MicahChen 写道 fengshihao 写道 fffvvvzz 写道 你把问题想复杂化了，单次循环，top100用红黑树，如果树大小小于100直接插入，否则比较树中最小值，大于则移去最小值，插入新值。
严重同意 呵呵 . 大顶堆 而已 . 哈哈，最大堆正解，头100个节点不断构造就可以了 精辟 |
| 返回顶楼 | |
|
发表时间：2010-04-01
kdlan 写道 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作成一个最小堆还能再快点 我找了下资料试了下反而效率很差，估计是我对最小堆使用还有问题，能否提供个该题最小堆的代码，谢谢！ 不过我原来的算法也确实还有不少优化空间，比如前100个数可以减少比较、数组排序还可优化 |
| 返回顶楼 | |
|
发表时间：2010-04-01
用TreeSet，做单循环一次是个不错的思路
将回帖中的代码改一改，我这个一般情况只要889-951ms之间了
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
public class TestSF {
public static Set<Integer> getTop100(int[] inputArray) {
TreeSet<Integer> top100 = new TreeSet<Integer>();
Integer objs = null;
for (int i = 0; i < inputArray.length; i++) {
if (top100.size() < 100) {
top100.add(inputArray[i]);
continue ;
}
if(objs==null)
{
objs = top100.first();
}
if ( objs < inputArray[i]) {
top100.remove(objs);
top100.add(inputArray[i]);
objs = top100.first();
}
}
return top100;
}
public static void main(String[] args) {
int numberCount = 100000000;
int maxNumber = numberCount;
int inputArray[] = new int[numberCount];
Random random = new Random();
for (int i = 0; i < numberCount; ++i) {
inputArray[i] = Math.abs(random.nextInt(maxNumber));
}
System.out.println("Sort begin...");
long current = System.currentTimeMillis();
Set<Integer> result = TestSF.getTop100(inputArray);
System.out.println("Spend time:"+ (System.currentTimeMillis() - current));
}
}
|
| 返回顶楼 | |
|
发表时间：2010-04-01
这样的考题，我遇过多次了。其实这类题，考官考的东西并不完全是算法。完全追求算法，就陷进去了。考题考的是两方面，一是考虑内存，纯粹用排序算法是不可能的，光int[] nums = new int[100000000];这一句就可能导致内存不够。（增加内存根本不是考官希望的，这么个小程序就要增加内存？）二是考虑在内存许可的情况下，尽量提高速度。
方法1 基本上，这道题如果不考虑数据录入，调用两次循环，上亿的数字中找top100，用不到1秒应该就够了。 提示： 1.考虑用位（bit）数组，1亿bit需要多少内存？100000000/1024/1024/8<12M，就是10亿数字，也不到120M 2.一个bit的数组大小为1亿，bit[i]=0,表示i数据不存在，bit[i]＝1，表示i数据存在。（循环1次1亿数据，不用比较数据大小） 3.最后找到bit数组中，bit[i]＝1且top100 i（循环1次） 方法2 建立一张数据库表，把上亿数据录入数据库，有索引的情况下，在上亿数据中找top100，也是很快的（不考虑数据录入数据库的时间） |
| 返回顶楼 | |
