文章目录
- 前言
- 牛客-寻找第K大、LeetCode215. 数组中的第K个最大元素【中等】
- 题目及类型
- 思路
- 思路1:大顶堆
- 思路2:快排+二分+随机基准点
前言
博主所有博客文件目录索引:博客目录索引(持续更新)
牛客-寻找第K大、LeetCode215. 数组中的第K个最大元素【中等】
题目及类型
相同题目:215. 数组中的第K个最大元素
题目链接:寻找第K大
题目内容:有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。给定一个整数数组 a ,同时给定它的大小n和要找的 k ,请返回第 k 大的数(包括重复的元素,不用去重),保证答案存在。
类型:大顶堆、快排+二分
思路
思路1:大顶堆
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();}
}
思路2:快排+二分+随机基准点
最佳思路:快排+二分+随机基准点。在快排的过程中不断的找到对应的基准点,然后以这个基准点比较k(基准点的左边是>该基准点的,这样我们才能将基准点的索引与第k大的索引来进行比较)
思路:快排+二分+随机基准点
复杂度分析:
- 时间复杂度:O(n.logn)
- 空间复杂度:O(n)
一个探索思路的过程:
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+1while (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大,那么从小到大的顺序就是kreturn 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