设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
解题方案方法一排序（冒泡/选择）
思路
1，冒泡排序是每执行一次，就会确定最终位置，执行k次后，就可以得到结果，时间复杂度为o(n * k),当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问题的详细内容。