标题: [Microsoft面试]查找最小的k 个元素 [打印本页] 作者: 王鹏 时间: 2013-8-16 10:34 标题: [Microsoft面试]查找最小的k 个元素 题目：输入n 个整数，输出其中最小的k 个。例如输入1，2，3，4，5，6，7 和8 这8 个数字，则最小的4 个数字为1，2，3 和4。作者: 陈荣莲 时间: 2013-8-16 10:45
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[0...n-1] 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[j]<a) i = j; if (a < a[p]) 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[l+1] < a[l]) l++; if (a[l] < a) swap(a, i, l); i=l; }}