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循环取出队列元素存入数组。
网友评论