TOP K问题,

　　00-1010问题解决方案方法一、方法二、方法三

　　00-1010求k的最小数

　　设计一个算法，找出数组中k的最小个数。你可以以任何顺序返回这些k数。

　　//冒泡排序public static int[]topkbybubble(int[]arr，int k){ int[]ret=new int[k]；if(k==0 arr . length==0){ ret ret；} for(int I=0；我k；I){ for(int j=arr . length-1；j I；j - ) { if (arr[j] arr[j 1]) { swap(arr，j，j 1)；} } ret[i]=arr[i]。ret返回；}//Select公共静态int [] topkbyselect (int [] arr，int k){ int[]ret=new int[k]；for(int I=0；我k；I){ int maxIndex=I；int maxNum=arr[max index]；for(int j=I 1；j排列长度；j){ if(arr[j]maxNum){ maxIndex=j；maxNum=arr[j]；} } if (maxIndex！=i) { swap(arr，maxIndex，I)；} ret[I]=arr[I]；ret返回；} public static void swap(int[] arr，int a，int b){ int temp=arr[a]；arr[a]=arr[b]；arr[b]=temp；}

　　00-1010各个击破-快速排序

　　思考

　　1.快速排序的核心是分而治之的思想。首先通过分而治之划分将序列分成两部分，然后再次递归执行这两部分；

　　2.利用分而治之的思想，即划分操作分区，根据主元素pivot调整顺序，将较大的放在左端，较小的放在右端，从而确定主元素pivotIndex的位置。如果pivotIndex正好是k-1，那么第一个k-1位置的编号就是我们需要的顶部K。

　　时间复杂度为3360o (n)

　　代码实现

　　public static int[]topKByPartition(int[]arr，int k){ if(arr . length==0 k=0){ return new int[0]；} return quickSort(arr，0，arr.length-1，k)；}//快速排序公共静态int []快速排序(int [] arr，int low，int high，int k){ int n=arr . length；int pivotIndex=partition(arr，low，high)；if(pivotIndex==k-1){ return arrays . copyofrage(arr，0，k)；} else if(pivotIndex k-1){ return quick sort(arr，low，pivotIndex-1，k)；}else { return quickSort(arr，pivotIndex 1，high，k)；} }公共静态int partition(int[] arr，int low，int high){ if(high-low==0){ return low；} int pivot=arr[high]；int left=低；int right=high-1；while(左右){ while(左右arr[左]pivot){ left；} while(left right arr[right]pivot){ right-；} if(左右){ swap(arr，left，right)；} else { break} } swap(arr，high，left)；向左返回；}public static void swap(int[] arr，int a，int b){ int temp=arr[a]；arr[a]=arr[b]；arr[b]=temp；}

　　00-1010利用堆

　　思考

　　1.建立一个最大堆。

　　2.遍历原始数组并对元素进行排队。当堆的大小为K时，只需要比较最上面的元素和下一个元素。如果它大于顶部元素，则删除顶部元素并将其插入堆中，直到遍历完所有元素。

　　3.将存储在队列中的k个数出队

　　时间复杂度：O(N*logK)

　　代码实现

　　public class TopK { public int[]small estk(int[]arr，int k){ int[]ret=new int[k]；if(k==0 arr . length==0){ ret ret；} //1、构建一个最大堆//JDK的优先级队列是最小堆，所以我们需要使用我们的比较器队列Integer Queue=New Priority Queue(New Comparator Integer(){ @ override public int compare(Integer O1，Integer O2){ Return O2-O1；} });//2，遍历原数组，入队for(int value : arr){ if(queue . size()k){ queue . offer(value)；} else { if(value queue . peek()){ queue . poll()；queue.offer(值)；}}} //3，将存放在队列中的k个元素出队for(int I=0；我k；I){ ret[I]=queue . poll()；ret返回；}}}就这样。本文对Java中Top-K问题的深入分析和解决方法介绍如下。更多相关Java Top-K内容，请搜索热门IT之前的文章或者继续浏览下面的相关文章。我希望你以后能更多地支持流行音乐！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

TOP K问题,

目录

相关文章阅读