微信公众号接口文档,广州网站优化指导,a5源码,商城网站如何建设文章目录 前言牛客-寻找第K大、LeetCode215. 数组中的第K个最大元素【中等】题目及类型思路思路1#xff1a;大顶堆思路2#xff1a;快排二分随机基准点 前言
博主所有博客文件目录索引#xff1a;博客目录索引(持续更新) 牛客-寻找第K大、LeetCode215. 数组中的第K个最大元… 文章目录 前言牛客-寻找第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;}PriorityQueueInteger 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;}//目标找到大于基准值的//注意这里jl1while (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
