题目链接

题目描述

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

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

解题思路

1. 直接排序

很明显，如果数组是有序的，那么数组索引下标为 nums.length - k 的元素就是数组中第 K 个最大元素。

注意：在面试中遇到此问题肯定不是考这种解决方法。

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

时间复杂度：，取决于对数组进行排序的排序算法的时间复杂度。
空间复杂度：。
2. 堆结构

利用堆排序解决——建立一个大根堆，做 k - 1 次删除操作后堆顶元素就是数组中的第 K 个最大元素。

注意：

在 Java 中可以直接使用优先队列 PriorityQueue 作为大根堆，但是在面试中，使用该方法更多考察的对堆结构的实现。（下面给出使用优先队列的代码实现，但不推荐）
需要掌握「建堆」、「调整堆」和「删除」过程。
优先队列——最大堆

使用优先队列作为大根堆的代码实现：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                return b - a;
            }
        });
        for (int i = 0; i < nums.length; i++) {
            maxHeap.add(nums[i]);
        }
        // 做 k - 1 次删除操作
        for (int i = 0; i < k - 1; i++) {
            maxHeap.poll();
        }
        return maxHeap.peek();
    }
}

构建最大堆

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        // 构建堆
        for (int i = heapSize / 2 - 1; i >= 0; i--) {
            downAdjust(nums, i, heapSize);
        }
        // 做 k - 1 次删除操作，每次删除后调整堆
        for (int i = nums.length - 1; i >= nums.length - k + 1; i--) {
            swap(nums, 0, i);
            downAdjust(nums, 0, i);
        }
        return nums[0];
    }
    public void downAdjust(int[] nums, int index, int heapSize) {
        int cIndex = index * 2 + 1;
        while (cIndex < heapSize) {
            if (cIndex + 1 < heapSize && nums[cIndex + 1] > nums[cIndex]) {
                cIndex++;
            }
            if (nums[index] > nums[cIndex]) {
                break;
            }
            swap(nums, index, cIndex);
            index = cIndex;
            cIndex = index * 2 + 1;
        }
    }
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

时间复杂度：，建堆的时间代价是，删除的总代价是。
空间复杂度：。
优先队列——最小堆

其实只需要建立大小为 K 的最小堆就可以找到数组中的第 K 个最大元素。遍历数组，当数组元素大于栈顶元素就将栈顶元素删除并把该元素加入堆中，遍历结束后栈顶元素就是第 K 大元素。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new Comparator<>() {
            public int compare(Integer a, Integer b) {
                return a - b;
            }
        });
        for (int i = 0; i < k; i++) {
            minHeap.add(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            // 当前元素大于堆顶元素
            if (nums[i] > minHeap.peek()) {
                minHeap.poll();
                minHeap.add(nums[i]);
            }
        }
        // 最后堆顶元素就是第 K 大
        return minHeap.poll();
    }
}

时间复杂度：，堆中只存在 K 个元素。
空间复杂度：

还可以对上述代码进行优化，只使用一个 for 循环来完成。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new Comparator<>() {
            public int compare(Integer a, Integer b) {
                return a - b;
            }
        });
        for (int num : nums) {
            // 堆中已经有 k 各元素并且当前元素比堆顶元素小，那就不添加
            if (minHeap.size() > k && num < minHeap.peek()) continue;
            minHeap.add(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.poll();
    }
}

构建最小堆

class Solution {
    public int findKthLargest(int[] nums, int k) {
        for (int i = k / 2 - 1; i >= 0; i--) {
            downAdjust(nums, i, k);
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] < nums[0]) continue;
            swap(nums, i, 0);
            downAdjust(nums, 0, k);
        }
        return nums[0];
    }
    public void downAdjust(int[] nums, int index, int size) {
        int cIndex = index * 2 + 1;
        while (cIndex < size) {
            if (cIndex + 1 < size && nums[cIndex + 1] < nums[cIndex]) {
                cIndex++;
            }
            if (nums[index] < nums[cIndex]) {
                break;
            }
            swap(nums, index, cIndex);
            index = cIndex;
            cIndex = index * 2 + 1;
        }
    }
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

基于快速排序的选择算法

算过流程：

设数组长度为 length。快速排序中，通过 partition 函数，将一个基准元素（假设下标为 j）划分成以下两个部分：

nums[0]...nums[j - 1] 区间内的所有元素都小于等于 nums[j]；
nums[j + 1]...nums[length - 1] 区间内的所有元素都大于等于 nums[j]。

经过一次划分，一定可以确定一个元素的最终位置，假设对于 nums[j] 的最终位置为 m。而数组中第 K 个最大元素的下标为 length - K，当我们某一次划分后确定了某一个元素的位置等于 length - K时，就说明找到了数组中第 K 个最大元素。

注意：对于极端用例可能会导致快速排序时间复杂度退化至 LeetCode215. 数组中第 K 个最大元素 - 图10 ，所以最好随机选择基准元素。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int target = nums.length - k;
        return quickSelect(nums, 0, nums.length - 1, target);
    }
    public int quickSelect(int[] nums, int lo, int hi, int target) {
        if (lo > hi) {
            return nums[lo];
        }
        int rand = lo + (int)(Math.random() * (hi - lo + 1));
        swap(nums, rand, lo);
        int pivotIndex = partition(nums, lo, hi);
        if (pivotIndex == target) {
            return nums[pivotIndex];
        } else if (target > pivotIndex) {
            return quickSelect(nums, pivotIndex + 1, hi, target);
        } else {
            return quickSelect(nums, lo, pivotIndex - 1, target);
        }
    }
    public int partition(int[] nums, int lo, int hi) {
        int left = lo;
        int right = hi;
        int pivot = nums[lo];
        while (left < right) {
            while (left < right && nums[right] > pivot) {
                right--;
            }
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            if (left < right) {
                swap(nums, left, right);
            }
        }
        nums[lo] = nums[left];
        nums[left] = pivot;
        return left;
    }
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

时间复杂度：
空间复杂度：

LeetCode215. 数组中第 K 个最大元素