力扣 215. 数组中的第K个最大元素

题目来源：https://leetcode.cn/problems/kth-largest-element-in-an-array/

大致题意：
找出未排序数组中第 k 大的元素

思路

如果要找出数组中第 k 大的元素，最简单的方法就是直接排序，然后按照索引取出第 k 大的元素即可

不过题目并未要求将数组排序，直接排序会有冗余操作

较优的方法由根据堆排序的思想，每轮选出当前堆最大元素，时间复杂度为 O(log n)，经过 k 次后选出的最大元素即为第 k 大元素，这样时间复杂度为 O(k * log n)

上述方法也有缺陷，因为其相当于将最大的 k 个元素全部排序了

快排的分界方法，方法每执行一次就会确定一个元素在排序后数组中的位置

于是可以使用快排的分界方法来求第 k 大的元素，每次分界方法执行后确定的位置与 k 的关系有：

1. 当前位置等于 k，那么当前位置对应元素即为第 k 大元素
2. 当前位置小于 k，那么第 k 大元素应该在当前位置右侧，接下只用在右侧元素中找即可
3. 当前位置大于 k，那么第 k 大元素应该在当前位置左侧，接下只用在左侧元素中找即可

具体实现时，可以通过两个标志位 start 和 end 表示待寻找元素所在范围，初始时为 0 和 n - 1，接下来根据分界方法的分界位置与 k 的关系更新两个标志位

代码：

public class FindKthLargest {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        // 获取分界位置
        int ith = getPivot(nums, 0, n - 1);
        // 升序排序，需要将 k 转化为第 k 小的元素
        k = n - k;
        // 查找范围
        int start = 0;
        int end = n - 1;
        // 根据分界位置与 k 的关系更新两个标志位
        while (ith != k) {
            // 分界位置小于 k，往右侧找
            if (ith < k) {
                start = ith + 1;
                ith = getPivot(nums, start, end);
            } else {
                // 分界位置大于 k，往左侧找
                end = ith - 1;
                ith = getPivot(nums, start, end);
            }
        }
        return nums[ith];
    }

    // 获取当前数组首元素在 [left, right] 中的排序位置
    public int getPivot(int[] nums, int left, int right) {
        int l = left;
        int r = right;
        int pivot = nums[left];
        while (l < r) {
            while (l < r && nums[r] >= pivot) {
                r--;
            }
            nums[l] = nums[r];
            while (l < r && nums[l] <= pivot) {
                l++;
            }
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44