1.数组中第k大/前k大的元素（215-中）
示例：
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 输入: [3,2,1,5,6,4] 和 k = 2 输出: [5, 6]
思路：
法1：快排变形：类似传统快排，区别在于，我们每次进行划分得到的索引index，我们只需要比较该索引值与目标索引的大小，继续递归满足条件的区间，而不需要对整个数组进行排序；
法2：优先队列：直接利用java现成的PriorityQueue优先队列实现(默认小根堆)，维持有K个元素的小根堆，最终返回堆顶或者将堆中所有元素输出。
代码1：时间复杂度O(n)
// 数组中第k大元素 public int findKthLargest(int[] nums, int k) { if (nums == null || nums.length == 0 || k == 0) return 0; int target = nums.length - k; return quickSort(nums, 0, nums.length - 1, target); } private int quickSort(int[] nums, int l, int r, int target) { int index = partition(nums, l, r); if (index == target) return nums[index]; return index > target ? quickSort(nums, l, index - 1, target) : quickSort(nums, index + 1, r, target); } // 划分过程：一定要随机选取划分值！ private int partition(int[] nums, int l, int r) { swap(nums, l + (int)(Math.random() * (r - l + 1)), r); int less = l - 1, more = r; while (l < more) { if (nums[l] < nums[r]) { swap(nums, ++less, l++); } else if (nums[l] > nums[r]) { swap(nums, --more, l); } else { l++; } } swap(nums, more, r); return more; } public void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }
代码2：时间复杂度O(nlogk)
// 数组第k大元素的队列实现 public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int num : nums) { pq.add(num); // 维持小根堆大小为K if (pq.size() > k) { pq.poll(); } } return pq.peek(); } // 数组前k大元素的队列实现 public int[] largestK(int[] arr, int k) { if (arr == null || arr.length == 0 || k == 0) return new int[0]; Queue<Integer> pq = new PriorityQueue<>(); for (int num : arr) { pq.add(num); if (pq.size() > k) { pq.poll(); } } int[] ans = new int[pq.size()]; int index = 0; for (int i : pq) { ans[index++] = i; } return ans; }
2.数组中第k小/前k小个的元素（面试题）
示例：
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 输入： arr = [1,3,5,7,2,4,6,8], k = 4 输出： [1,2,3,4]
思路：
法1：快排变形：与上题思路相同，唯一不同的就是目标索引，数组中第k小/前k小个的元素为k - 1；
法2：优先队列：重写比较方法，维持有K个元素的小根堆，最终返回堆顶或者将堆中所有元素输出。
代码1：时间复杂度O(n)
// 数组中前k小的元素 public int[] smallestK(int[] arr, int k) { if (k == 0 || arr == null || arr.length == 0) return new int[0]; // 注意：第k小的元素下标为k - 1 return quickSort(arr, 0, arr.length - 1, k - 1); } private int[] quickSort(int[] arr, int l, int r, int k) { int index = partition(arr, l, r); if (index == k) { // 复制数组arr的前k个数，也就是0 - k-1 return Arrays.copyOf(arr, index + 1); } return index > k ? quickSort(arr, l, index - 1, k) : quickSort(arr, index + 1, r, k); } private int partition(int[] arr, int l, int r) { // 随机选取划分值 swap(arr, l + (int)(Math.random() * (r - l + 1)), r); int less = l - 1, pivot = arr[r]; for (int i = l; i < r; ++i) { if (arr[i] <= pivot) { swap(arr, ++less, i); } } swap(arr, less + 1, r); return less + 1; } public void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
代码2：时间复杂度O(nlogk)
// 数组第k小的队列实现 public int findKthSmallest(int[] nums, int k) { if (nums == null || nums.length == 0 || k == 0) return new int[0]; Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1); for (int num : nums) { pq.add(num); if (pq.size() > k) { pq.poll(); } } return pq.peek(); } // 前k小的元素 public int[] smallestK(int[] arr, int k) { if (arr == null || arr.length == 0 || k == 0) return new int[0]; Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1); for (int num : arr) { pq.add(num); if (pq.size() > k) { pq.poll(); } } int[] ans = new int[pq.size()]; int index = 0; for (int i : pq) { ans[index++] = i; } return ans; }
队列的add()方法和offer()方法的区别：
两者都是往队列尾部插入元素，不同的时候，当超出队列界限的时候，
- add（）方法是抛出异常让你处理，
- offer（）方法是直接返回false
总结
topk问题还有像线性查找算法（bfprt）等高效的算法，这里只介绍使用快排思路实现和优先级队列实现两种思路。
- 优先队列：代码简单，即遍历数组，维护一个大小为k的堆（面试可以先写出），但是时间复杂度较高O(NlogK)。
- 快排变形：关键是我们无需对不需要的区间进行排序，只需要找到目标值或者目标区间即可，可在O(N)时间复杂度解决问题。
对于快排变形：
- 数组中第k大/前k大的元素：目标索引为
nums.length - k； - 数组中第k小/前k小个的元素：目标索引为
k - 1。
对于优先队列：
- 数组中第k大/前k大的元素：使用小根堆（堆顶元素最小，PriorityQueue默认实现）；
- 数组中第k小/前k小个的元素：使用大根堆（堆顶元素）。
最终的返回区间结果：
- 快排变形：使用
Arrays.copyOf(arr, k)：返回arr数组的前k个数； - 优先队列：直接使用增强for循环取出队列元素存入数组。
参考鸣谢：
