声明：题目来自： http://blog.csdn.net/v_JULY_v/archive/2010/11/17/6015165.aspx JULY整理了100道微软等公司的面试题目，我想先不看答案： http://blog.csdn.net/v_JULY_v/archive/2011/01/10/6126406.aspx 自己先做一遍。
题目：
5. 查找最小的k 个元素
题目：输入n 个整数，输出其中最小的k 个。
例如输入1 ，2 ，3 ，4 ，5 ，6 ，7 和8 这8 个数字，则最小的4 个数字为1 ，2 ，3 和4 。
思路：
最简单的想法就是在内部分配一个K大小的数组，用于存储最小的K个数，这K个数从大到小排序 array[0..K-1]，那么每次读入一个新的数 elem, 我们比较elem 和 array[0], 如果elem>array[0], 则elem肯定不是最小的K个数的候选，否则(当elem<array[0])，我们找到第一个位置P, 使得array[P-1]>elem>array[P] , 然后： array[i]=array[i+1] for all i =(0..P-2); array[P-1] = elem.
但是这样并不好，如果给定的数组是从大到小排好顺序的，那么每次我们都要遍历整个内部数组，其时间复杂度是O(N2 ).
其实我们可以把题目重新理解为：
我需要一个数据结构，
条件1） 能够在O(1)时间判断一个新的数字是不是已有的K个数字中最大的
条件2 ) 如果不是现有的K个数中最大的话，我希望在最短时间内，丢弃现有K个数中的最大的那个数，放入新的数，并且最适当调整，使调整后的数据结构仍然满足 条件1).
结果就是 最大堆 （Max Binary Heap）. 对于Binary Heap,每次调整，最坏情况时间复杂度是 log(k)。 前K个元素不许要调整（因为我还没有开始建立堆结构），剩下N-K个元素，最坏情况为 (N-K)log(K)。
代码：
/* * 题目：输入n个整数，输出其中最小的k个。 例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。 */ public class MinNPicker { private int[] m_binaryHeap; private int m_numberChecked; //indicate how many elements have been checked public MinNPicker(int size){ m_numberChecked = 0; m_binaryHeap = new int[size]; } public void print(){ for(int i: m_binaryHeap){ System.out.println(i); } } public void add(int[] elems){ for(int i: elems){ add(i); } } public void reset(){ m_numberChecked = 0; } public void add(int elem){ if(m_numberChecked < m_binaryHeap.length){ m_binaryHeap[m_numberChecked++] = elem; if(m_numberChecked == m_binaryHeap.length){ //now let's construct the binary heap //for a binary heap of N size, N/2 to N elements are leaf nodes(leaf nodes are already heap) int smallestLeaf = m_binaryHeap.length/2; for(int i=smallestLeaf-1; i>=0; i--){ maxHeapify(m_binaryHeap, i); } } return; } if(elem < m_binaryHeap[0]){ //0 is the root, also the max element m_binaryHeap[0] = elem; maxHeapify(m_binaryHeap,0); } } private void maxHeapify(int[] array, int index){ //we use a max heap to contain only N elements, everytime we're feed a new element //if new elem > max elem within heap, we replace that ex-max elem and redo max-heapify //our internal array to hold the heap is 0-based, so left-child(i)=2i+1, right-child(i)=2i+2 //maxHeapipy assume that both left child and right child of i are already heap int largest = index; int size = array.length; int left = index*2 + 1; int right = index*2 + 2; if(left < size && array[index] < array[left]){ //! make sure left < size, otherwise exception //left child is bigger largest = left; } //now let's compare the right child and the largest if(right < size && array[largest] < array[right]){ largest = right; } //only swap when largest != index if(largest != index){ int tmp = array[index]; array[index] = array[largest]; array[largest] = tmp; //because we swap the content between index and largest, it's not sure if the original //left child/right child tree are still hold heap property //!!don't forget to recursive call maxHeapify itself maxHeapify(array,largest); } } public static void main(String[] args){ int[] givenElems = {8,7,6,5,4,3,2,1}; MinNPicker picker = new MinNPicker(4); picker.add(givenElems); picker.print(); System.out.println("-------"); int[] givenElems2 = {1,2,3,4,5,6,7,8}; picker.reset(); picker.add(givenElems2); picker.print(); } }
