博主所有博客文件目录索引:博客目录索引(持续更新)
相同题目:215. 数组中的第K个最大元素
题目链接:寻找第K大
题目内容:有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。给定一个整数数组 a ,同时给定它的大小n和要找的 k ,请返回第 k 大的数(包括重复的元素,不用去重),保证答案存在。
类型:大顶堆、快排+二分
class Solution {
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
PriorityQueue<Integer> queue = new PriorityQueue<>(k, (o1, o2)->o2.compareTo(o1));
for (int i = 0; i < nums.length; i++) {
queue.offer(nums[i]);
}
while (k > 1) {
queue.poll();
k--;
}
return queue.poll();
}
}
最佳思路:快排+二分+随机基准点。在快排的过程中不断的找到对应的基准点,然后以这个基准点比较k(基准点的左边是>该基准点的,这样我们才能将基准点的索引与第k大的索引来进行比较)
思路:快排+二分+随机基准点
复杂度分析:
一个探索思路的过程:
import java.util.*;
public class Solution {
private static int res;
Private static Random random = new Ramdom();
public int findKth(int[] a, int n, int K) {
quickSort(a, 0, n - 1, K);
return res;
}
public void quickSort(int[] a, int l, int r, int K) {
if (l > r) {
return;
}
int mid = partition(a, l, r);
//看这个基准点与K的位置是否相符
if (mid + 1 == K) {
res = a[mid];
}else if (mid + 1 < K) {
quickSort(a, mid + 1, r, K);
}else {
quickSort(a, 0, mid - 1, K);
}
}
public int partition(int[] a, int l, int r) {
int x = Math.abs(random.nextInt()) % (r - l + 1) + l;
swap(a, l, x);
int j = l;
for (int i = l + 1; i <= r; i++) {
if (a[i] >= a[l]) {
j++;
swap(a, i, j);
}
}
//交换基准点
swap(a, l, j);
return j;
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
不同的分块思路:
//方式一:
public int partition(int[] a, int l, int r) {
int x = Math.abs(random.nextInt()) % (r - l + 1) + l;
swap(a, l, x);
int j = l;
for (int i = l + 1; i <= r; i++) {
if (a[i] >= a[l]) {
j++;
swap(a, i, j);
}
}
//交换基准点
swap(a, l, j);
return j;
}
//方式二:
public int partition(int[] a, int l, int r) {
int v = a[l];
int i = l + 1;
int j = r;
while (true) {
//目标找到小于基准值的
while (i <= r && a[i] > v ) {
i++;
}
//目标找到大于基准值的
//注意:这里j>=l+1
while (j >= l + 1 && a[j] < v) {
j--;
}
if (i > j) {
break;
}
swap(a, i, j);
i++;
j--;
}
//交换基准点
swap(a, l, j);
return j;
}
写的好快排方式:
class Solution {
//大顶堆找
public int findKthLargest(int[] nums, int k) {
//由于找的是第k大,那么从小到大的顺序就是k
return quickFind(nums, 0, nums.length - 1, nums.length - k);
}
public int quickFind(int[] nums, int left, int right, int k) {
//基准点
int x = nums[left];
if (left == right) return nums[k];
int i = left - 1, j = right + 1;
while (i < j) {
do i ++; while (nums[i] < x);
do j --; while (nums[j] > x);
//交换
if (i < j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
//若是寻找的位置<=j,那么左范围进行递归
if (k <= j) {
return quickFind(nums, left, j, k);
}else { //右范围进行递归
return quickFind(nums, j + 1, right, k);
}
}
}
整理者:长路 时间:2024.1.14-15