devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

leetcode215. 数组中的第K个最大元素

作者：Monodyee | 2024-03-07 15:16:09

赞

踩

数组中的第k个最大元素

目录

方法一：暴力解法

方法二：借助 partition 操作定位到最终排定以后索引为 len - k 的那个元素（特别注意：随机化切分元素）

方法三：优先队列（默认是最大堆）

在未排序的数组中找到第 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 ≤ 数组的长度。

方法一：暴力解法


题目要求我们找到“数组排序后的第 kk 个最大的元素，而不是第 kk 个不同的元素” ，

语义是从右边往左边数第 kk 个元素（从 11 开始），那么从左向右数是第几个呢，我们列出几个找找规律就好了。

一共 66 个元素，找第 22 大，索引是 44；
一共 66 个元素，找第 44 大，索引是 22。
因此，升序排序以后，目标元素的索引是 len - k。这是最简单的思路，如果只答这个方法，面试官可能并不会满意，但是在我们平时的开发工作中，还是不能忽视这种思路简单的方法，理由如下：

最简单同时也一定是最容易编码的，编码成功的几率最高，可以用这个最简单思路编码的结果和其它思路编码的结果进行比对，验证高级算法的正确性；

在数据规模小、对时间复杂度、空间复杂度要求不高的时候，简单问题简单做；

思路简单的算法考虑清楚了，有些时候能为实现高级算法铺路，这道题也是如此；

低级算法往往容错性最好，即在输入不满足题目条件的时候，往往还能得到正确的答案，而高级算法对输入数据的要求就非常苛刻，这一点可以参考 「力扣」第 4 题：“寻找两个有序数组的中位数”。

参考代码 1：

  1. import java.util.Arrays;
  2.  
  3. public class Solution {
  4.  
  5.     public int findKthLargest(int[] nums, int k) {
  6.         int len = nums.length;
  7.         Arrays.sort(nums);
  8.         return nums[len - k];
  9.     }
  10. }

复杂度分析：

时间复杂度：O(N \log N)O(NlogN)，这里 NN 是数组的长度，算法的性能消耗主要在排序，JDK 默认使用快速排序，因此时间复杂度为 O(N \log N)O(NlogN)。
空间复杂度：O(1)O(1)，这里是原地排序，没有借助额外的辅助空间。
到这里，我们已经分析出了：

1、我们应该返回最终排定以后位于 len - k 的那个元素；
2、性能消耗主要在排序，JDK 默认使用快速排序。

学习过 “快速排序” 的朋友，一定知道一个操作叫 partition，它是 “分而治之” 思想当中 “分” 的那一步。经过 partition 操作以后，每一次都能排定一个元素，并且这个元素左边的数都不大于它，这个元素右边的数都不小于它，并且我们还能知道排定以后的元素的索引。于是可以应用 “减而治之”（分治思想的特例）的思想，把问题规模转化到一个更小的范围里。

于是得到方法二。

方法二：借助 partition 操作定位到最终排定以后索引为 len - k 的那个元素（特别注意：随机化切分元素）

参考代码 2：

  1. public class Solution {
  2.  
  3.     public int findKthLargest(int[] nums, int k) {
  4.         int len = nums.length;
  5.         int left = 0;
  6.         int right = len - 1;
  7.  
  8.         // 转换一下，第 k 大元素的索引是 len - k
  9.         int target = len - k;
  10.  
  11.         while (true) {
  12.             int index = partition(nums, left, right);
  13.             if (index == target) {
  14.                 return nums[index];
  15.             } else if (index < target) {
  16.                 left = index + 1;
  17.             } else {
  18.                 right = index - 1;
  19.             }
  20.         }
  21.     }
  22.  
  23.     /**
  24.      * 在数组 nums 的子区间 [left, right] 执行 partition 操作，返回 nums[left] 排序以后应该在的位置
  25.      * 在遍历过程中保持循环不变量的语义
  26.      * 1、[left + 1, j] < nums[left]
  27.      * 2、(j, i] >= nums[left]
  28.      *
  29.      * @param nums
  30.      * @param left
  31.      * @param right
  32.      * @return
  33.      */
  34.     public int partition(int[] nums, int left, int right) {
  35.         int pivot = nums[left];
  36.         int j = left;
  37.         for (int i = left + 1; i <= right; i++) {
  38.             if (nums[i] < pivot) {
  39.                 // 小于 pivot 的元素都被交换到前面
  40.                 j++;
  41.                 swap(nums, j, i);
  42.             }
  43.         }
  44.         // 在之前遍历的过程中，满足 [left + 1, j] < pivot，并且 (j, i] >= pivot
  45.         swap(nums, j, left);
  46.         // 交换以后 [left, j - 1] < pivot, nums[j] = pivot, [j + 1, right] >= pivot
  47.         return j;
  48.     }
  49.  
  50.     private void swap(int[] nums, int index1, int index2) {
  51.         int temp = nums[index1];
  52.         nums[index1] = nums[index2];
  53.         nums[index2] = temp;
  54.     }
  55. }

复杂度分析：

时间复杂度：O(N)O(N)，这里 NN 是数组的长度，理由可以参考本题解下用户 @ZLW 的评论，需要使用主定理进行分析。
空间复杂度：O(1)O(1)，原地排序，没有借助额外的辅助空间。
注意：本题必须随机初始化 pivot 元素，否则通过时间会很慢，因为测试用例中有极端测试用例。

为了应对极端测试用例，使得递归树加深，可以在循环一开始的时候，随机交换第 11 个元素与它后面的任意 11 个元素的位置；

说明：最极端的是顺序数组与倒序数组，此时递归树画出来是链表，时间复杂度是 O(N^2)，根本达不到减治的效果。

参考代码 3：

  1. import java.util.Random;
  2.  
  3. public class Solution {
  4.  
  5.     private static Random random = new Random(System.currentTimeMillis());
  6.  
  7.     public int findKthLargest(int[] nums, int k) {
  8.         int len = nums.length;
  9.         int target = len - k;
  10.         int left = 0;
  11.         int right = len - 1;
  12.         while (true) {
  13.             int index = partition(nums, left, right);
  14.             if (index < target) {
  15.                 left = index + 1;
  16.             } else if (index > target) {
  17.                 right = index - 1;
  18.             } else {
  19.                 return nums[index];
  20.             }
  21.         }
  22.     }
  23.  
  24.     // 在区间 [left, right] 这个区间执行 partition 操作
  25.  
  26.     private int partition(int[] nums, int left, int right) {
  27.         // 在区间随机选择一个元素作为标定点
  28.         if (right > left) {
  29.             int randomIndex = left + 1 + random.nextInt(right - left);
  30.             swap(nums, left, randomIndex);
  31.         }
  32.  
  33.         int pivot = nums[left];
  34.         int j = left;
  35.         for (int i = left + 1; i <= right; i++) {
  36.             if (nums[i] < pivot) {
  37.                 j++;
  38.                 swap(nums, j, i);
  39.             }
  40.         }
  41.         swap(nums, left, j);
  42.         return j;
  43.     }
  44.  
  45.     private void swap(int[] nums, int index1, int index2) {
  46.         int temp = nums[index1];
  47.         nums[index1] = nums[index2];
  48.         nums[index2] = temp;
  49.     }
  50. }

2、使用双指针，将与 pivot 相等的元素等概论地分到 pivot 最终排定位置的两边。

参考代码 4：使用双指针的办法找到切分元素的位置。

  1. import java.util.Random;
  2.  
  3. public class Solution {
  4.  
  5.     private static Random random = new Random(System.currentTimeMillis());
  6.  
  7.     public int findKthLargest(int[] nums, int k) {
  8.         int len = nums.length;
  9.         int left = 0;
  10.         int right = len - 1;
  11.  
  12.         // 转换一下，第 k 大元素的索引是 len - k
  13.         int target = len - k;
  14.  
  15.         while (true) {
  16.             int index = partition(nums, left, right);
  17.             if (index == target) {
  18.                 return nums[index];
  19.             } else if (index < target) {
  20.                 left = index + 1;
  21.             } else {
  22.                 right = index - 1;
  23.             }
  24.         }
  25.     }
  26.  
  27.     public int partition(int[] nums, int left, int right) {
  28.         // 在区间随机选择一个元素作为标定点
  29.         if (right > left) {
  30.             int randomIndex = left + 1 + random.nextInt(right - left);
  31.             swap(nums, left, randomIndex);
  32.         }
  33.  
  34.         int pivot = nums[left];
  35.  
  36.         // 将等于 pivot 的元素分散到两边
  37.         // [left, lt) <= pivot
  38.         // (rt, right] >= pivot
  39.  
  40.         int lt = left + 1;
  41.         int rt = right;
  42.  
  43.         while (true) {
  44.             while (lt <= rt && nums[lt] < pivot) {
  45.                 lt++;
  46.             }
  47.             while (lt <= rt && nums[rt] > pivot) {
  48.                 rt--;
  49.             }
  50.  
  51.             if (lt > rt) {
  52.                 break;
  53.             }
  54.             swap(nums, lt, rt);
  55.             lt++;
  56.             rt--;
  57.         }
  58.  
  59.         swap(nums, left, rt);
  60.         return rt;
  61.     }
  62.  
  63.     private void swap(int[] nums, int index1, int index2) {
  64.         int temp = nums[index1];
  65.         nums[index1] = nums[index2];
  66.         nums[index2] = temp;
  67.     }
  68. }

方法三：优先队列（默认是最大堆）


优先队列的思路是很朴素的。因为第 K 大元素，其实就是整个数组排序以后后半部分最小的那个元素。因此，我们可以维护一个有 K 个元素的最小堆：

1、如果当前堆不满，直接添加；

2、堆满的时候，如果新读到的数小于等于堆顶，肯定不是我们要找的元素，只有新都到的数大于堆顶的时候，才将堆顶拿出，然后放入新读到的数，进而让堆自己去调整内部结构。

说明：这里最合适的操作其实是 replace，即直接把新读进来的元素放在堆顶，然后执行下沉（siftDown）操作。Java 当中的 PriorityQueue 没有提供这个操作，只好先 poll() 再 offer()。

优先队列的写法就很多了，这里例举一下我能想到的（以下的写法大同小异，没有本质差别）。

假设数组有 len 个元素。

思路1：把 len 个元素都放入一个最小堆中，然后再 pop() 出 len - k 个元素，此时最小堆只剩下 k 个元素，堆顶元素就是数组中的第 k 个最大元素。

思路2：把 len 个元素都放入一个最大堆中，然后再 pop() 出 k - 1 个元素，因为前 k - 1 大的元素都被弹出了，此时最大堆的堆顶元素就是数组中的第 k 个最大元素。

根据以上思路，分别写出下面的代码：

参考代码 5：

  1. import java.util.PriorityQueue;
  2.  
  3. public class Solution {
  4.  
  5.     public int findKthLargest(int[] nums, int k) {
  6.         int len = nums.length;
  7.         // 使用一个含有 len 个元素的最小堆，默认是最小堆，可以不写 lambda 表达式：(a, b) -> a - b
  8.         PriorityQueue<Integer> minHeap = new PriorityQueue<>(len, (a, b) -> a - b);
  9.         for (int i = 0; i < len; i++) {
  10.             minHeap.add(nums[i]);
  11.         }
  12.         for (int i = 0; i < len - k; i++) {
  13.             minHeap.poll();
  14.         }
  15.         return minHeap.peek();
  16.     }
  17. }

参考代码 6：

  1. import java.util.PriorityQueue;
  2.  
  3. public class Solution {
  4.  
  5.     public int findKthLargest(int[] nums, int k) {
  6.         int len = nums.length;
  7.         // 使用一个含有 len 个元素的最大堆，lambda 表达式应写成：(a, b) -> b - a
  8.         PriorityQueue<Integer> maxHeap = new PriorityQueue<>(len, (a, b) -> b - a);
  9.         for (int i = 0; i < len; i++) {
  10.             maxHeap.add(nums[i]);
  11.         }
  12.         for (int i = 0; i < k - 1; i++) {
  13.             maxHeap.poll();
  14.         }
  15.         return maxHeap.peek();
  16.     }
  17. }
  18.

思路 3：只用 k 个容量的优先队列，而不用全部 len 个容量。

参考代码 7：

  1. import java.util.PriorityQueue;
  2.  
  3. public class Solution {
  4.  
  5.     public int findKthLargest(int[] nums, int k) {
  6.         int len = nums.length;
  7.         // 使用一个含有 k 个元素的最小堆
  8.         PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
  9.         for (int i = 0; i < k; i++) {
  10.             minHeap.add(nums[i]);
  11.         }
  12.         for (int i = k; i < len; i++) {
  13.             // 看一眼，不拿出，因为有可能没有必要替换
  14.             Integer topEle = minHeap.peek();
  15.             // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
  16.             if (nums[i] > topEle) {
  17.                 minHeap.poll();
  18.                 minHeap.add(nums[i]);
  19.             }
  20.         }
  21.         return minHeap.peek();
  22.     }
  23. }
  24.

参考代码 8：

  1. import java.util.PriorityQueue;
  2.  
  3. public class Solution {
  4.  
  5.     public int findKthLargest(int[] nums, int k) {
  6.         int len = nums.length;
  7.         // 最小堆
  8.         PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k + 1, (a, b) -> (a - b));
  9.         for (int i = 0; i < k; i++) {
  10.             priorityQueue.add(nums[i]);
  11.         }
  12.         for (int i = k; i < len; i++) {
  13.             priorityQueue.add(nums[i]);
  14.             priorityQueue.poll();
  15.         }
  16.         return priorityQueue.peek();
  17.     }
  18. }
  19.

思路 5：综合考虑以上两种情况，总之都是为了节约空间复杂度。即 k 较小的时候使用最小堆，k 较大的时候使用最大堆。

参考代码 9：

  1. import java.util.PriorityQueue;
  2.  
  3. public class Solution {
  4.  
  5.     // 根据 k 的不同，选最大堆和最小堆，目的是让堆中的元素更小
  6.     // 思路 1：k 要是更靠近 0 的话，此时 k 是一个较大的数，用最大堆
  7.     // 例如在一个有 6 个元素的数组里找第 5 大的元素
  8.     // 思路 2：k 要是更靠近 len 的话，用最小堆
  9.  
  10.     // 所以分界点就是 k = len - k
  11.  
  12.     public int findKthLargest(int[] nums, int k) {
  13.         int len = nums.length;
  14.         if (k <= len - k) {
  15.             // System.out.println("使用最小堆");
  16.             // 特例：k = 1，用容量为 k 的最小堆
  17.             // 使用一个含有 k 个元素的最小堆
  18.             PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
  19.             for (int i = 0; i < k; i++) {
  20.                 minHeap.add(nums[i]);
  21.             }
  22.             for (int i = k; i < len; i++) {
  23.                 // 看一眼，不拿出，因为有可能没有必要替换
  24.                 Integer topEle = minHeap.peek();
  25.                 // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
  26.                 if (nums[i] > topEle) {
  27.                     minHeap.poll();
  28.                     minHeap.add(nums[i]);
  29.                 }
  30.             }
  31.             return minHeap.peek();
  32.  
  33.         } else {
  34.             // System.out.println("使用最大堆");
  35.             assert k > len - k;
  36.             // 特例：k = 100，用容量为 len - k + 1 的最大堆
  37.             int capacity = len - k + 1;
  38.             PriorityQueue<Integer> maxHeap = new PriorityQueue<>(capacity, (a, b) -> b - a);
  39.             for (int i = 0; i < capacity; i++) {
  40.                 maxHeap.add(nums[i]);
  41.             }
  42.             for (int i = capacity; i < len; i++) {
  43.                 // 看一眼，不拿出，因为有可能没有必要替换
  44.                 Integer topEle = maxHeap.peek();
  45.                 // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
  46.                 if (nums[i] < topEle) {
  47.                     maxHeap.poll();
  48.                     maxHeap.add(nums[i]);
  49.                 }
  50.             }
  51.             return maxHeap.peek();
  52.         }
  53.     }
  54. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/206246
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号