首页 > 代码库 > 最大的K个数
最大的K个数
建立最大的k个数，可以通过快速排序来实现，也可以通过堆排序来实现。我们来看堆排序的实现过程。
其中，也是有两种思路：第一种思路是：把数组里的所有的数建堆（O(nlogn)），然后交换k次，通过堆排序实现。(klogn)
时间复杂度是：O((n+k)logn) = O(nlogn)
第二种思路是：先用前面的k个数来建最小堆，堆顶元素将会是这个堆里的最小值，然后从第K+1个数开始和堆顶元素进行比较，若此值比堆顶元素小，则这个数比大的至少有k个元素，这个值肯定不是最大的k个数；若此值比堆顶元素大，则这个数有可能是最大的k个数，调整这个堆即可。最后建立的堆就是所求的最大的k个数，并且堆顶元素就是最大的k个数中的最小值。
时间复杂度是：（O(klogk)+O(n-k)logk） = O(nlogk)
第二种思路的代码：
public int[] heapSort(int[] array,int k){ int length = array.length; for(int i=(k-2/2);i>=0;i--){ //先建立具有K个元素的大顶堆 adjustHeap(array,i,k-1); } for(int i=k;i<array.length;i++){ //比较n-K次 if(array[0]>array[i]) { swap(array,0,i); adjustHeap(array,0,k-1); } } return array; } public void adjustHeap(int[] array,int m,int n){ while(2*m+1<=n){ int p = 2*m+1; if(p<n){ if(array[p]<array[p+1]){ p=p+1; } } if(array[m]<array[p]){ swap(array,m,p); m = p; }else{ break; } } } public void swap(int[] array,int p,int q){ int temp = array[q]; array[q] = array[p]; array[p] = temp; }
最大的K个数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。