寻找第 K 大的数 爱被打了一巴掌 2022-12-05 04:51 174阅读 0赞 # 寻找第 K 大的数 # ## 1、参考资料 ## https://leetcode-cn.com/problems/kth-largest-element-in-an-array/ https://www.jianshu.com/p/33ee33ce8699 ## 2、题目要求 ## > **题目描述** 在未排序的数组中找到第 **k** 个最大的元素。请注意，你需要找的是数组排序后的第 `k` 个最大的元素，而不是第 `k` 个不同的元素。 > **示例 1:** 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 > **示例 2:** 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 > **说明:** 你可以假设 `k` 总是有效的，且 1 ≤ k ≤ 数组的长度。 ## 3、代码思路 ## 缩减版的快排 1. 刚开始肯定会想到使用快排，先对 `nums` 数组进行快速排序，然后再返回第 `k` 大的数： `nums[index]`，其中 `index` 为倒数第 `k` 个元素的下标：`index=nums.length-k` 2. 仔细想想，因为我们只需要求取第 `k` 的数，其实完全不用对整个数组进行快排，可以使用阉割版的快排 3. 我们调用 `partition = int partition(int[] arr, int left, int right) {` 函数将数组分为左右两半，其实就已经可以排除掉一部分元素，将不需要进行排序的数组区间剔除 -------------------- 剔除无需排序的区间：我们需要判断 `partition` 与 `index`的关系 1. 调用 `partition()` 函数后，在 `partition` 左边的元素都小于等于 `arr[partition]`，在 `partition` 右边的元素都大于等于 `arr[partition]`。 2. 如果 `partition = index`，恭喜，运气不错，说明第 `k` 大的元素恰好就在 `partition` 处，已经找到第 `k` 大的元素，结束递归 3. 如果 `partition > index`，则说明第 `k` 大的元素在 `[partition+1, right]` 之间，对该区间进行递归快排 4. 如果 `partition < index`，则说明第 `k` 大的元素在 `[left, partition-1]` 之间，对该区间进行递归快排 -------------------- 时间复杂度近似为 `O(n)` ## 4、代码实现 ## 代码：寻找第 `K` 大的数 class Solution { public int findKthLargest(int[] nums, int k) { quickSortK(nums, 0, nums.length - 1, nums.length - k); return nums[nums.length - k]; } private void quickSortK(int[] arr, int left, int right, int index) { // 如果 left >= right，则证明此条路径的递归快排完成 if (left < right) { // 将数组分为左右两半，partition 就是中间的分界线 int partition = partition(arr, left, right); if (partition == index) { // 如果 partition == index，则说明 partition 就是第 k 大的元素 return; } else if (partition > index) { // 如果 partition > index，则说明第 k 大的元素在区间左边，在左半区间递归进行快排 quickSortK(arr, left, partition - 1, index); } else { // 如果 partition < index，则说明第 k 大的元素在区间右边，在右半区间递归进行快排 quickSortK(arr, partition + 1, right, index); } } } // 将数组分为左右两半 private int partition(int[] arr, int left, int right) { int pivot = arr[left]; //终止while循环以后left和right一定相等的 while (left < right) { while (left < right && arr[right] >= pivot) { --right; } arr[left] = arr[right]; while (left < right && arr[left] <= pivot) { ++left; } arr[right] = arr[left]; } arr[left] = pivot; //left可以改为right return left; } } 下面是快排的代码，来和原版的快排对比一下 private static void quickSort(int[] arr, int left, int right) { if (left < right) { int partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex - 1); quickSort(arr, partitionIndex + 1, right); } } private static int partition(int[] arr, int left, int right) { int pivot = arr[left]; //终止while循环以后left和right一定相等的 while (left < right) { while (left < right && arr[right] >= pivot) { --right; } arr[left] = arr[right]; while (left < right && arr[left] <= pivot) { ++left; } arr[right] = arr[left]; } arr[left] = pivot; //right可以改为left return left; }
还没有评论，来说两句吧...