[Microsoft面试]查找最小的k 个元素
题目：输入n 个整数，输出其中最小的k 个。例如输入1，2，3，4，5，6，7 和8 这8 个数字，则最小的4 个数字为1，2，3 和4。 This isa very traditional question...O(nlogn): cat I_FILE | sort -n | head -n KO(kn): do insertion sort until k elements are retrieved.O(n+klogn): Take O(n) time to bottom-up build a min-heap. Then sift-down k-1times.So traditional that I don’t want to write the codes...Only gives the siftup and siftdown function./***@paramithe index of the element in heap a to be sifted upvoid siftup(int a[], int i, int n) {while (i>0) { int j=(i&1==0 ? i-1 : i+1); int p=(i-1)>>1; if (j<n && a<a) i = j; if (a < a) swap(a, i, p); i = p;} }void siftdown(int a[], int i, int n) { while (2*i+1<n){ int l=2*i+1; if (l+1<n && a < a) l++; if (a < a) swap(a, i, l); i=l;}}
页:
[1]