LeetCode 215. Kth Largest Element in an Array

题目描述

• Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
  For example,
  Given [3,2,1,5,6,4] and k = 2, return 5.
• 地址

问题分析

• 这是十分经典的 Top K 问题。和剑指offer-最小的K个数类似
• 方法一：堆
  用一个大小为K的最小堆，先将数组中前K个元素入堆，然后继续遍历数组中其他元素，若当前元素大于堆顶元素，便将堆顶弹出，将当前元素入堆。这样，最终，堆里便是该数组中最大的K个数，堆顶元素便是第 K大的数。
  时间复杂度：O(NlogK)
  同理，如果找第K小的数字，便维护一个大小为K的大根堆，若当前元素小与对顶元素，便将堆顶弹出，将当前元素入堆。这样，最终，堆里便是该数组中最小的K个数，堆顶元素便是第 K小的数。
• 方法2：Quick Select
  类似于快排。就是不断优化pivot所在的位置，最终使pivot位于 nums.length - k 处。这样nums[nums.length - k] 便是 第K大的数字。
  复杂度分析：平均为O(N),最差情况下为 O(N^2)
  

经验教训

• 解决 Top k 问题的两大思路
• Quick Select 复杂度分析

代码实现

• 最小堆

    public int findKthLargest(int[] nums, int k) {
        if (nums == null || k <= 0 || k > nums.length) {
            return -1;
        }
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int i = 0;
        while (i < k) {
            minHeap.add(nums[i++]);
        }
        while (i < nums.length) {
            if (nums[i] > minHeap.peek()) {
                minHeap.poll();
                minHeap.add(nums[i]);
            }
            i++;
        }
        return minHeap.peek();
    }

• Quick Select

    public int findKthLargest(int[] nums, int k) {
        if (nums == null || k <= 0 || k > nums.length) {
            return -1;
        }
        int begin = 0;
        int end = nums.length - 1;
        while (begin <= end) {
            int pivotIndex = partition(nums, begin, end);
            if (pivotIndex > nums.length - k) {
                end = pivotIndex - 1;
            }else if (pivotIndex < nums.length - k) {
                begin = pivotIndex + 1;
            }else {
                return nums[pivotIndex];
            }
        }
        return -1;
    }

    public int partition(int[] nums, int begin, int end) {
        int pivot = nums[begin];
        while (begin < end) {
            while (begin < end && nums[end] >= pivot) {
                end--;
            }
            nums[begin] = nums[end];
            while (begin < end && nums[begin] <= pivot) {
                begin++;
            }
            nums[end] = nums[begin];
        }
        nums[begin] = pivot;
        return begin;
    }