答复: 阿里巴巴面试感言

好吧，我承认我闲的蛋疼
问题：3000万条的记录取最大的前50条数据
这题的时间复杂度应该是3000W*lg50
需要取前50个数构造heap恒长为50的最小堆
第51个数开始，与根节点比较，如果大于根节点，与根节点交换，并进行一次最小堆的minHeapify过程
内存2G很宽裕
代码如下（PS:我是没时间做3000W的数据，除非我真的蛋疼）

package org.leon.testcase;

public class Main {
	public static void main(String[] args) {
		int[] target = {12,4,3,56,11,122,131,312,2,3321,3,4,13,1,231,3,4,5,6,5,34,3};
		int[] ary = new int[5];
		int j=0;
		MinHeap heap = new MinHeap();
		for (int i = 0; i < target.length; i++) {
			if(j<5){
				ary[j]=target[i];
				j++;
				continue;
			}
			if(j==5){
				heap.builtMinHeap(ary);
			}
			if(ary[0]<target[i]){
				ary[0]=target[i];
				heap.minHeapify(ary,0);
			}
		}
		for (int i = 0; i < ary.length; i++) {
			System.out.println(ary[i]);
		}
	}
}
class MinHeap {

	@SuppressWarnings("unused")
	private int parent(int i) {
		if (i == 0)
			return -1;
		return i / 2;
	}

	private int left(int i) {
		if (i == 0)
			return 1;
		return 2 * i;
	}

	private int right(int i) {
		if (i == 0)
			return 2;
		return 2 * i + 1;
	}

	public void minHeapify(int[] ary, int i) {
		int l = left(i);
		int r = right(i);
		int min = i;
		if (l < ary.length) {
			if (ary[l] < ary[i]) {
				min = l;
			}
		}
		if (r < ary.length) {
			if (ary[r] < ary[min]) {
				min = r;
			}
		}
		if (min != i) {
			int temp = ary[i];
			ary[i] = ary[min];
			ary[min] = temp;
			minHeapify(ary, min);
		}
	}

	public void builtMinHeap(int[] a) {
		for (int i = (a.length - 1) / 2; i >= 0; i--) {
			minHeapify(a, i);
		}
	}
}

评论

4 楼 huangfenghit 2011-11-04  

你绝对的大牛~

3 楼 yiminghe 2009-10-10  

这个好多方法的，这种算是比较好的，编程之美有一章讲的这个，面试没新意

2 楼 leon_a 2009-10-10  

liuxuan620 写道

哈哈，应该是用最大堆-----要求的是前k个最小的

我囧了，反正就是这么个思路

1 楼 liuxuan620 2009-10-10  

哈哈，应该是用最大堆-----要求的是前k个最小的