215. Kth Largest Element in an Array

题目描述和难度

题目描述：

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

题目难度：中等。
英文网址：215. Kth Largest Element in an Array 。
中文网址：215. 数组中的第K个最大元素。

思路分析

求解关键：这是一个常见的问题。其实把数组排个序（升序），返回倒数第 $k$ 个数就可以了。但是如果出现在笔试的时候，这个答案肯定不能过关的，我看到过的解答中，使用 partition 和堆也是需要掌握的。

首先，借用快速排序的 partition 的思想完成。关键在于理解 partition 的返回值，返回值是拉通了整个数组的索引值。

partition 这个函数返回的是整个数组的第 k 个最小元素（从 0 开始计算）。
如果找第 k 个最小元素，即第 n - k 个最大元素。

例如：给定数组为：[2,5,6,1,4,7] ，一共 6 个元素找 k = 2，如果返回 4 ，就可以返回了。给定数组为：[2,5,6,1,4,7] ，一共 6 个元素找 k = 2，如果返回 2 ，左边的区间就可以不用看了。

参考解答

参考解答1：使用快速排序的 partition 的思想完成。

public class Solution2 {

    private static Random random = new Random(System.currentTimeMillis());

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        if (len == 0 || k > len) {
            throw new IllegalArgumentException("参数错误");
        }
        // 转换一下，这样比较好操作
        // 第 k 大元素的索引是 len - k
        int target = len - k;
        int l = 0;
        int r = len - 1;
        while (true) {
            int i = partition(nums, l, r);
            if (i < target) {
                l = i + 1;
            } else if (i > target) {
                r = i - 1;
            } else {
                return nums[i];
            }
        }
    }

    // 在区间 [left, right] 这个区间执行 partition 操作
    private int partition(int[] nums, int left, int right) {
        // 在区间随机选择一个元素作为标定点（以下这两行代码非必需）
        // 这一步优化非必需
        if (right > left) {
            int randomIndex = left + 1 + random.nextInt(right - left);
            swap(nums, left, randomIndex);
        }

        int pivot = nums[left];
        int l = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                l++;
                swap(nums, l, i);
            }
        }
        swap(nums, left, l);
        return l;
    }

    private void swap(int[] nums, int index1, int index2) {
        if (index1 == index2) {
            return;
        }
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

Python 写法：

class Solution:

    # 数组中的第 K 个最大元素
    # 数组中第 k 大的元素，它的索引是 len(nums) - k
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """

        left = 0
        right = len(nums) - 1

        while True:
            index = self.__partition(nums, left, right)
            if index == len(nums) - k:
                return nums[index]
            if index > len(nums) - k:
                right = index - 1
            else:
                left = index + 1

    def __partition(self, nums, left, right):
        """
        partition 是必须要会的子步骤，一定要非常熟练
        典型的例子就是：[3,7,8,1,2,4]
        遇到比第一个元素大的或等于的，就放过，遇到小的，就交换
        在 [left,right] 这个区间执行 partition
        :param nums:
        :param left:
        :param right:
        :return:
        """
        pivot = nums[left]
        k = left
        for index in range(left + 1, right + 1):
            if nums[index] < pivot:
                k += 1
                nums[k], nums[index] = nums[index], nums[k]
        nums[left], nums[k] = nums[k], nums[left]
        return k

参考解答2：使用最小堆，这个写法是我最开始的写法，有点死板。

public class Solution3 {

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        if (len == 0 || k > len) {
            throw new IllegalArgumentException("参数错误");
        }
        // 使用一个含有 k 个元素的最小堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, (a, b) -> a - b);
        for (int i = 0; i < k; i++) {
            priorityQueue.add(nums[i]);
        }
        for (int i = k; i < len; i++) {
            // 看一眼
            Integer topEle = priorityQueue.peek();
            // 只要当前遍历的元素比堆顶元素大，堆顶出栈，遍历的元素进去
            if (nums[i] > topEle) {
                priorityQueue.poll();
                priorityQueue.add(nums[i]);
            }
        }
        return priorityQueue.peek();
    }
}

Python 的写法：

import heapq


# 还可以参考：https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/167837/Python-or-tm

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        L = []
        for index in range(k):
            heapq.heappush(L, nums[index])
        for index in range(k, len(nums)):
            top = L[0]
            if nums[index] > top:
                heapq.heapreplace(L, nums[index])
        return L[0]

最小堆更简单的写法。

Java 写法：

public class Solution3 {

    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k + 1, (a, b) -> (a - b));
        for (int num : nums) {
            priorityQueue.add(num);
            if(priorityQueue.size()==k+1){
                priorityQueue.poll();
            }
        }
        return priorityQueue.peek();
    }
}

参考解答3：使用最大堆，这里要做一些简单的处理。

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0215-kth-largest-element-in-an-array ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。