这篇文章主要介绍“Java怎么解决Top-K的问题”,在日常操作中,相信很多人在Java怎么解决Top-K的问题问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Java怎么解决Top-K的问题”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
求最小的K个数
设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。
排序(冒泡/选择)
思路
1,冒泡排序是每执行一次,就会确定最终位置,执行K次后,就可以得到结果,时间复杂度为O(n * k),当k<<n时,O(n * k)的性能会比O(N*logN)好。
2,选择排序每执行依次,就会通过确定一个最大的或最小的放在一端,通过选择排序,执行K次就可以得到最大的K个数了。时间复杂度时O(N * K)。
代码实现
//冒泡排序 public static int[] topKByBubble(int[] arr, int k) { int[] ret = new int[k]; if (k == 0 || arr.length == 0) { return ret; } for (int i = 0; i < 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]; } return ret; } //选择排序 public static int[] topKBySelect(int[] arr, int k) { int[] ret = new int[k]; for (int i = 0; i < k; i++) { int maxIndex = i; int maxNum = arr[maxIndex]; for (int j = i + 1; j < arr.length; j++) { if (arr[j] > maxNum) { maxIndex = j; maxNum = arr[j]; } } if (maxIndex != i) { swap(arr, maxIndex, i); } ret[i] = arr[i]; } return ret; } public static void swap(int[] arr, int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; }
分治-快速排序
思路
1,快速排序的核心是分治思想,先通过分治partition把序列分为两个部分,再将两个部分进行再次递归;
2,利用分治思想,即划分操作partition,根据主元素pivot调整序列,比pivot大的放在左端,比pivot小的放在右端,这样确定主元素pivot的位置pivotIndex,如果pivotIndex刚好是k-1,那么前k-1位置的数就是前k大的元素,即我们要求的top K。
时间复杂度: O(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); } //快速排序 public static int[] quickSort(int[] arr, int low, int high, int k){ int n = arr.length; int pivotIndex = partition(arr, low, high); if(pivotIndex == k-1){ return Arrays.copyOfRange(arr,0,k); }else if(pivotIndex > k-1){ return quickSort(arr,low,pivotIndex-1,k); }else { return quickSort(arr,pivotIndex+1,high,k); } } public static int partition(int[] arr, int low, int high){ if(high - low == 0){ return low; } int pivot = arr[high]; int left = low; int right = high-1; while (left < right){ while (left < right && arr[left] > pivot){ left++; } while (left < right && arr[right] < pivot){ right--; } if(left < right){ swap(arr,left,right); }else { break; } } swap(arr,high,left); return left; } public static void swap(int[] arr,int a, int b){ int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; }
利用堆
思路
1,构建一个最大堆
2,遍历原数组,元素入队,当堆的大小为K时,只需要将堆顶元素于下一个元素比较,如果大于堆顶元素,则将堆顶元素删除,将该元素插入堆中,直到遍历完所有元素
3,将queue存储的K个数出队
时间复杂度:为O(N*logK)
代码实现
public class TopK { public int[] smallestK(int[] arr, int k) { int[] ret = new int[k]; if(k==0 || arr.length==0){ return ret; } // 1,构建一个最大堆 // JDK的优先级队列是最小堆, 就要用到我们比较器 Queue<Integer> queue = new PriorityQueue<>(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(value); } } } //3,将queue中存储的K个元素出队 for(int i = 0;i < k;i++){ ret[i] = queue.poll(); } return ret; } }
到此,关于“Java怎么解决Top-K的问题”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。