【Leetcode 热题 100】215. 数组中的第K个最大元素

问题配景

给定整数数组                                    n                         u                         m                         s                              nums                  nums 和整数                                    k                              k                  k，请返回数组中第                                    k                              k                  k 个最大的元素。
请注意，你需要找的是数组排序后的第                                    k                              k                  k 个最大的元素，而不是第                                    k                              k                  k 个不同的元素。
你必须计划并实现时间复杂度为                                    O                         (                         n                         )                              O(n)                  O(n) 的算法办理此问题。
数据约束

•                                         1                            ≤                            k                            ≤                            n                            u                            m                            s                            .                            l                            e                            n                            g                            t                            h                            ≤                            1                                       0                               5                                            1 \le k \le nums.length \le 10 ^ 5                     1≤k≤nums.length≤105
  
•                                         −                            1                                       0                               4                                      ≤                            n                            u                            m                            s                            [                            i                            ]                            ≤                            1                                       0                               4                                            -10 ^ 4 \le nums \le 10 ^ 4                     −104≤nums≤104
  

解题过程

经典求第                                   k                              k                  k大，最佳方案是用随机选择算法，时间复杂度大致是                                    O                         (                         N                         )                              O(N)                  O(N) 这个量级。
考虑到标题分类在堆，那除了调用 API 快速处理的方法之外，再写一下手撕堆看成练习。
干系详细的先容，可以参考 随机快排与随机选择 以及 堆排序与堆操作。
具体实现

使用堆 API

1. class Solution {
2.     public int findKthLargest(int[] nums, int k) {
3.         Queue<Integer> queue = new PriorityQueue<>();
4.         for(int num : nums) {
5.             queue.offer(num);
6.         }
7.         for(int i = 0; i < nums.length - k; i++) {
8.             queue.poll();
9.         }
10.         return queue.peek();
11.     }
12. }

复制代码

自己实现堆

1. class Solution {
2.     public int findKthLargest(int[] nums, int k) {
3.         int n = nums.length;
4.         buildHeap(nums);
5.         // 注意这里要修正索引
6.         while(k - 1 > 0) {
7.             swap(nums, 0, --n);
8.             downAdjust(nums, 0, n);
9.             k--;
10.         }
11.         return nums[0];
12.     }
14.     // 交换数组中的两个元素
15.     private void swap(int[] arr, int i, int j) {
16.         int temp = arr[i];
17.         arr[i] = arr[j];
18.         arr[j] = temp;
19.     }
20.    
21.     // 由上而下调整元素
22.     private void downAdjust(int[] arr, int cur, int size) {
23.         // 数组下标从零开始，当前节点的左孩子下标为 2 * cur + 1
24.         int child = 2 * cur + 1;
25.         while (child < size) {
26.             // 如果当前节点有右孩子，那么比较两个子节点的值确定潜在的交换对象
27.             int target = child + 1 < size && arr[child + 1] > arr[child] ? child + 1 : child;
28.             // 再与当前节点比较大小
29.             target = arr[target] > arr[cur] ? target : cur;
30.             // 一旦发现此次操作中无需交换，立即停止流程
31.             if (target == cur) {
32.                 break;
33.             }
34.             // 交换父子节点
35.             swap(arr, target, cur);
36.             // 移动工作指针
37.             cur = target;
38.             child = 2 * cur + 1;
39.         }
40.     }
41.    
42.     // 自底向顶建堆
43.     private void buildHeap(int[] arr) {
44.         int n = arr.length;
45.         for (int i = n - 1; i >= 0; i--) {
46.             downAdjust(arr, i, n);
47.         }
48.     }
49. }

复制代码

随机选择

1. class Solution {
2.     // 全局变量 first 表示等于当前元素的第一个下标位置，last 表示最后一个
3.     private static int first, last;
4.    
5.     public int findKthLargest(int[] nums, int k) {
6.         return randomizedSelect(nums, nums.length - k);
7.     }
9.     // 交换数组中的两个元素
10.     private void swap(int[] arr, int i, int j) {
11.         int temp = arr[i];
12.         arr[i] = arr[j];
13.         arr[j] = temp;
14.     }
16.     private void partition(int[] arr, int left, int right, int pivot) {
17.         // 初始化维护的指针
18.         first = left;
19.         last = right;
20.         int cur = left;
21.         // 注意循环到工作指针超越 last 即可结束流程
22.         while (cur <= last) {
23.             if (arr[cur] == pivot) {
24.                 cur++; // 当前元素等于划分标准，不作处理并后移指针
25.             } else if (arr[cur] < pivot) {
26.                 swap(arr, first++, cur++); // 小于划分标准，交换且分别后移两个指针
27.             } else {
28.                 swap(arr, cur, last--); // 大于划分标准，交换并前移记录最后一个当前元素的指针
29.             }
30.         }
31.     }
32.    
33.     private int randomizedSelect(int[] arr, int target) {
34.         int res = 0;
35.         for (int left = 0, right = arr.length - 1; left <= right;) {
36.             partition(arr, left, right, arr[left + (int) (Math.random() * (right - left + 1))]);
37.             if (target < first) {
38.                 right = first - 1; // 当前下标小于维护的第一个下标，到左边区间中找
39.             } else if (target > last) {
40.                 left = last + 1; // 当前下标大于维护的最后一个下标，到右边区间中找
41.             } else {
42.                 res = arr[target]; // 当前下标在维护的范围内，记录结果
43.                 break;
44.             }
45.         }
46.         return res;
47.     }
48. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。