215. 数组中的第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 ≤ 数组的长度。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解 :

  • 如题，此题目有三种思路，以下我们分别介绍这三种解题方法

image-20200629135827048

思路一 : 暴力法

  • 思路简单，数组全排序
  • 再取倒数第 k 个即可
1
2
3
4
5
6

    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;

        Arrays.sort(nums);
        return nums[nums.length - k];
    }

复杂度分析 :

时间复杂度 : O(N * log N) 此题目的时间主要消耗在 sort 快排上，而快排的时间复杂度为 O(N * log N)

空间复杂度 : O(1) 没有使用额外的存储空间

系统的 sort库函数还是非常强悍的，最差的时间复杂度都能击败 92.63% 的人，膜拜.

截屏2020-06-29下午2.01.50

思路二 : 二叉堆

  • 二叉堆经常用于解决 top K 问题
  • 求 第 k 个最大元素时，使用 小顶堆
  • 而二叉堆 在 Java中的实现是 优先级队列
  • 堆中元素数量维持在 k 个
  • 遍历数组，依次入堆，当堆中元素 > k时，堆顶元素移除
  • 遍历完 N 个元素， 堆中剩余 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

public int findKthLargest2(int[] nums, int k) {
    if (nums == null || nums.length == 0) return 0;
    int res = 0;

    // 优先级队列
    // 小顶堆
    // 小顶堆中维持 k 个元素
    // N 个元素依次加入小丁堆。 当小丁堆中元素数量 > k时, 移除堆顶
    // 遍历完 N 个元素，堆中剩余 K 个元素，堆顶即是最终结果
    PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    });

    for (int i = 0; i < nums.length; i++) {
        queue.add(nums[i]);
        if (queue.size() > k){
            queue.poll();
        }
    }

    res = queue.peek();
    return res;
}

复杂度分析 :

时间复杂度 :O(N * log K) : 堆中元素下滤 siftdown 操作 复杂度为 O(log K), 总共有 N 次操作。 所以总的时间复杂度为 O(N * log K)

空间复杂度 : O(K) 使用了额外的 堆，存储 K 个元素，所有空间复杂度为 O(K)

按道理讲, 使用堆的复杂度应该比全排序要好才对，然而在执行耗时上，却跟我们预想的不一样，如图：

截屏2020-06-29下午2.09.54

思路三 : 快排减治思想

  • 首先我们来回忆一下快排的执行流程
    • 随机选择数组中一个元素作为轴点元素 pivot
    • 遍历数组
      • 把比 pivot 小的元素 放在 pivot 的左边
      • 把把 pivot 大的元素 放在 pivot 的右边
    • 遍历完后，再分别对 pivot 左右两边的元素都执行以上操作
  • 本解法就是用的这种思想
    • 随机选择一个轴点元素 pivot
    • 依然是遍历数组，把 小于 pivot 的元素 放左边，大于 pivot 的元素放右边
    • 当轴点 pivot 元素右边元素数量刚好等于 k - 1时。 pivot 就是第 K 个最大元素
    • 当轴点 pivot 元素右边元素数量 > k - 1时, 在 左边 查找
    • 当轴点 pivot 元素右边元素数量 < k - 1时, 在 右边 查找
 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
45
46
47
48
49
50
51
52
53
54
55
56

/**
     *
     * 快排减治思想
     *
     * */
    public int findKthLargest3(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;

        return findKthLargestHelper(nums, 0, nums.length - 1, nums.length - k);
    }

    public int findKthLargestHelper(int[] nums, int begain, int end, int targetIdx){

      	// 轴点元素下标
        int pivotIdx = pivotIndex(nums, begain, end);
        // 当轴点元素下标 正好是 targetIdx
        // 则 此元素就是我们要找的结果
        if (pivotIdx == targetIdx) return nums[pivotIdx];
        // 当轴点元素下标 > targetIdx
        // 说明 轴点元素 > 第 K 个元素。 在 轴点左边查找
        if (pivotIdx > targetIdx){
            return findKthLargestHelper(nums, begain, pivotIdx - 1, targetIdx);
        }else {
          	// 当轴点元素 < targetIdx
          	// 说明 轴点元素 < 第 K 个元素， 在 轴点右边查找
            return findKthLargestHelper(nums, pivotIdx + 1, end, targetIdx);
        }
    }

		// 找轴点元素
    public int pivotIndex(int[] nums, int begain, int end){
				
        int tmp = nums[begain];
        boolean isright = true;

        while (begain < end){
            if (isright){
                if (nums[end] > tmp){
                    end --;
                }else {
                    nums[begain ++] = nums[end];
                    isright = false;
                }
            }else {
                if (nums[begain] < tmp){
                    begain ++;
                }else {
                    nums[end --] = nums[begain];
                    isright = true;
                }
            }
        }
        nums[begain] = tmp;
        return begain;
    }

复杂度分析 :

平均时间复杂度 : O(N)

最坏时间复杂度 : O(N ^ 2)

空间复杂度 : O(log N)) 递归深度 log N 层，占用 logN 的栈空间

⚠️⚠️⚠️

  • 理论上，快排思想的减治排序时间复杂度是最低的，为什么耗时最久呢？
  • 大概率是因为，测试用例中有极端的测试用例，完全升序的数组，会使得时间复杂度降低为最坏时间复杂度 O(N ^ 2)
  • 所以此题目中，我们必须使用 随机化轴点元素 来避免最坏时间复杂度的情况。
  • 这也一方面解释了，为什么 系统库函数sort 比 堆排 耗时少。
    • 堆排序 对完全有序的数组，依然按部就班的入堆
    • 而库函数Sort, 对完全有序的数组排序进行了优化。 使时间复杂度降低.

给予快排减治思想的随机轴点

  • 我们在思路三的基础上，增加了随机化
 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

/**
 *
 * 快排减治思想
 *
 * 加随机
 *
 * */
Random random = new Random();
public int findKthLargest3(int[] nums, int k) {
    if (nums == null || nums.length == 0) return 0;

    return findKthLargestHelper(nums, 0, nums.length - 1, nums.length - k);
}

public int findKthLargestHelper(int[] nums, int begain, int end, int targetIdx){

    int pivotIdx = pivotIndex(nums, begain, end);
    if (pivotIdx == targetIdx) return nums[pivotIdx];
    if (pivotIdx > targetIdx){
        return findKthLargestHelper(nums, begain, pivotIdx - 1, targetIdx);
    }else {
        return findKthLargestHelper(nums, pivotIdx + 1, end, targetIdx);
    }
}

public int pivotIndex(int[] nums, int begain, int end){

    if (end > begain) {
        int randomIndex = begain + 1 + random.nextInt(end - begain);
        swap(nums, begain, randomIndex);
    }

    int tmp = nums[begain];
    boolean isright = true;

    while (begain < end){
        if (isright){
            if (nums[end] > tmp){
                end --;
            }else {
                nums[begain ++] = nums[end];
                isright = false;
            }
        }else {
            if (nums[begain] < tmp){
                begain ++;
            }else {
                nums[end --] = nums[begain];
                isright = true;
            }
        }
    }
    nums[begain] = tmp;
    return begain;
}

public void swap(int[] nums, int i1, int i2){
    int tmp = nums[i1];
    nums[i1] = nums[i2];
    nums[i2] = tmp;
}

复杂度分析 :

平均时间复杂度 : O(N)

空间复杂度 : O(log N)

执行效率上，有了明显的提升，如图：

截屏2020-06-29下午3.22.48