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

题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

1
2
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

1
2
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
1
2
3
4
提示：

1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104

思路

  1. 对数组全部排序玩后，拿到第k个最大的数

  2. 使用快排的变形，如果基准值右边的数大于k了，我们就把左边的数抛弃，如果基准值就是k，我们已经不用排序了

实现

整体排序

1
2
3
4
5
6
private static class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

快排+筛选

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
private static class Solution2 {
        int k;

        public int findKthLargest(int[] nums, int k) {
            this.k = k;
            quiteSort(nums, 0, nums.length - 1);
            return nums[nums.length - k];
        }

        private void quiteSort(int[] nums, int low, int high) {
            if (low >= high) {
                return;
            }

            int left = low;
            int right = high;
            int index = (int) (Math.random() * (right - left) + left);
            int temp = nums[left];
            nums[left] = nums[index];
            nums[index] = temp;
            int standard = nums[left];


            while (left < right) {
                while (left < right && nums[right] >= standard) {
                    right--;
                }
                nums[left] = nums[right];
                while (left < right && nums[left] <= standard) {
                    left++;
                }
                nums[right] = nums[left];
            }
            nums[left] = standard;
            if (left == nums.length - k) {
                return;
            }
            if (left > nums.length - k) {
                quiteSort(nums, low, left - 1);
            }
            quiteSort(nums, left + 1, high);
        }
    }