输入n个整数，输出其中最小的k个

上一篇 / 下一篇  2011-11-10 22:29:35 / 个人分类：常见基础知识

查看( 1271 ) / 评论( 0 ) / 评分( 0 / 0 )
  1. /** 
  2.  * 题目：输入n个整数，输出其中最小的k个。 
  3.  * 例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。 
  4.  * 这道题最简单的思路莫过于把输入的n个整数排序，这样排在最前面的k个数就是最小的k个数。只是这种思路的时间复杂度为O(nlogn)。 
  5.  * 题目并没有要求要查找的k个数，甚至后n-k个数是有序的，既然如此，咱们又何必对所有的n个数都进行排序列? 
  6.        这时，咱们想到了用选择或插入排序，即遍历n个数，先把最先遍历到得k个数存入大小为k的数组之中，对这k个数，进行排序，找到k个数中的最大数kmax， 
  7.   k1<k2,K3<…<kmax（kmax设为k个元素的数组中最大元素），用时O（k），后再继续遍历后n-k个数，x与kmax比较，如果x<kmax，则x代替kmax，并再次排序k个元素的数组。如果x>kmax，则不更新数组。 
  8.        这样，每次更新或不更新数组的所用的时间为O（k）或O（0），整趟下来，总的时间复杂度平均下来为：n*O（k）=O（n*k）。 
  9. 3、  当然，更好的办法是维护k个元素的最大堆，原理与上述第3个方案一致，即用容量为k的最大堆存储最小的k个数，此时，k1<k2<...<kmax（kmax设为大顶堆中最大元素）。 
  10. 遍历一次数列，n，每次遍历一个元素x，与堆顶元素比较，x<kmax，更新堆（用时logk），否则不更新堆。这样下来，总费时O（n*logk）。此方法得益于在堆中，查找等各项操作时间复杂度均为logk（不然，就如上述思路2所述：直接用数组也可以找出前k个小的元素，用时O（n*k））。 
  11.  */  
  12. public class MinK {  
  13.   
  14.     /** 
  15.      *  
  16.      * @param krr 
  17.      * @param k 
  18.      * @return 
  19.      */  
  20.     public static int[] minK(int krr[],int k){  
  21.         int arr[] = new int[k];  
  22.         for(int i = 0;i<k;i++)  
  23.             arr[i] = krr[i];  
  24.         buildHeap(arr);  
  25.         for(int j = k;j<krr.length;j++){  
  26.             if(krr[j]<arr[0]){  
  27.                 arr[0] = krr[j];  
  28.                 maxHeap(arr,1,k);  
  29.             }  
  30.         }  
  31.         return arr;  
  32.     }  
  33.     /** 
  34.      * 建最大堆 
  35.      * @param arr 
  36.      */  
  37.     public static void buildHeap(int arr[]){  
  38.         int heapsize = arr.length;  
  39.         for(int i=arr.length/2;i>0;i--)  
  40.             maxHeap(arr,i,heapsize);  
  41.     }  
  42.     /** 
  43.      * 调整为最大堆 
  44.      * @param arr 
  45.      * @param i 
  46.      * @param heapsize 
  47.      */  
  48.     public static void maxHeap(int arr[],int i,int heapsize){  
  49.         int largest = i;  
  50.         int left = 2*i;  
  51.         int right = 2*i+1;  
  52.         if(left<=heapsize&&arr[i-1]<arr[left-1])  
  53.             largest = left;  
  54.         if(right<=heapsize&&arr[largest-1]<arr[right-1])  
  55.             largest = right;  
  56.         if(largest!=i){  
  57.             int temp = arr[i-1];  
  58.             arr[i-1] = arr[largest-1];  
  59.             arr[largest-1] = temp;  
  60.             maxHeap(arr,largest,heapsize);  
  61.         }  
  62.     }  
  63.     public static void main(String[] args) {  
  64.         int krr[] = {1,3,4,2,7,8,9,10,14,16};  
  65.         int arr[] = minK(krr,4);  
  66.         for(int i =0;i<arr.length;i++)  
  67.             System.out.println(arr[i]);  
  68.   
  69.     }  
  70.   
  71. }  

收藏 举报

TAG:

 

评分：0

我来说两句

日历

« 2024-05-14  
日 一 二 三 四 五 六
   1234
567891011
12131415161718
19202122232425
262728293031 

数据统计

  • 访问量: 11135
  • 日志数: 18
  • 建立时间: 2011-11-07
  • 更新时间: 2011-12-06

RSS订阅

Open Toolbar