牛客-寻找第K大、LeetCode215. 数组中的第K个最大元素【中等】

前言

博主所有博客文件目录索引：博客目录索引(持续更新)

---

牛客-寻找第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