Top k问题的讨论（三种方法的java实现及适用范围）

￡神魔★判官ぃ 2022-07-16 02:47 160阅读 0赞

在很多的笔试和面试中，喜欢考察Top K.下面从自身的经验给出三种实现方式及实用范围。

*  合并法

这种方法适用于几个数组有序的情况，来求Top k。时间复杂度为O(k\*m)。(m:为数组的个数）.具体实现如下：

/** * 已知几个递减有序的m个数组，求这几个数据前k大的数 *适合采用Merge的方法,时间复杂度(O(k*m); */
    import java.util.List; import java.util.Arrays; import java.util.ArrayList; public class TopKByMerge{ public int[] getTopK(List<List<Integer>>input,int k){ int index[]=new int[input.size()];//保存每个数组下标扫描的位置;
     int result[]=new int[k]; for(int i=0;i<k;i++){ int max=Integer.MIN_VALUE; int maxIndex=0; for(int j=0;j<input.size();j++){ if(index[j]<input.get(j).size()){ if(max<input.get(j).get(index[j])){ max=input.get(j).get(index[j]); maxIndex=j; } } } if(max==Integer.MIN_VALUE){ return result; } result[i]=max; index[maxIndex]+=1; } return result; }

*  快排过程法

快排过程法利用快速排序的过程来求Top k.平均时间复杂度为（O(k\*logn).适用于无序单个数组。具体java实现如下：

/* *利用快速排序的过程来求最小的k个数 * */
    public class TopK{ int partion(int a[],int first,int end){ int i=first; int main=a[end]; for(int j=first;j<end;j++){ if(a[j]<main){ int temp=a[j]; a[j]=a[i]; a[i]=temp; i++; } } a[end]=a[i]; a[i]=main; return i; } void getTopKMinBySort(int a[],int first,int end,int k){ if(first<end){ int partionIndex=partion(a,first,end); if(partionIndex==k-1)return; else if(partionIndex>k-1)getTopKMinBySort(a,first,partionIndex-1,k); else getTopKMinBySort(a,partionIndex+1,end,k); } } public static void main(String []args){ int a[]={
       2,20,3,7,9,1,17,18,0,4}; int k=6; new TopK().getTopKMinBySort(a,0,a.length-1,k); for(int i=0;i<k;i++){ System.out.print(a[i]+" "); } } }

*  采用小根堆或者大根堆

求最大K个采用小根堆，而求最小K个采用大根堆。

求最大K个的步奏：

1.      根据数据前K个建立K个节点的小根堆。
2.      在后面的N-K的数据的扫描中，

*  如果数据大于小根堆的根节点，则根节点的值覆为该数据，并调节节点至小根堆。
 *  如果数据小于或等于小根堆的根节点，小根堆无变化。

求最小K个跟这求最大K个类似。时间复杂度O(nlogK)(n:数据的长度),特别适用于大数据的求Top K。

/** * 求前面的最大K个 解决方案：小根堆 (数据量比较大（特别是大到内存不可以容纳）时，偏向于采用堆) * * */
    public class TopK { /** * 创建k个节点的小根堆 * * @param a * @param k * @return */
     int[] createHeap(int a[], int k) { int[] result = new int[k]; for (int i = 0; i < k; i++) { result[i] = a[i]; } for (int i = 1; i < k; i++) { int child = i; int parent = (i - 1) / 2; int temp = a[i]; while (parent >= 0 &&child!=0&& result[parent] >temp) { result[child] = result[parent]; child = parent; parent = (parent - 1) / 2; } result[child] = temp; } return result; } void insert(int a[], int value) { a[0]=value; int parent=0; while(parent<a.length){ int lchild=2*parent+1; int rchild=2*parent+2; int minIndex=parent; if(lchild<a.length&&a[parent]>a[lchild]){ minIndex=lchild; } if(rchild<a.length&&a[minIndex]>a[rchild]){ minIndex=rchild; } if(minIndex==parent){ break; }else{ int temp=a[parent]; a[parent]=a[minIndex]; a[minIndex]=temp; parent=minIndex; } } } int[] getTopKByHeap(int input[], int k) { int heap[] = this.createHeap(input, k); for(int i=k;i<input.length;i++){ if(input[i]>heap[0]){ this.insert(heap, input[i]); } } return heap; } public static void main(String[] args) { int a[] = { 4, 3, 5, 1, 2,8,9,10}; int result[] = new TopK().getTopKByHeap(a, 3); for (int temp : result) { System.out.println(temp); } } }