题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

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

示例 2:

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

解法一：快速选择

类似与快速排序，随机选择一个基准pivot，将小于pivot的元素全放在左边，大于pivot的元素全放在右边，并返回pivot所在位置index。每进行一次选择就会确定一个元素的位置，index==n-k表明nums[index]就是第k大元素。如果index<n-k，则在index+1到right区间继续选择；index>n-k，则在left到index-1区间继续选择.

import java.util.Random;


class Solution {
    private final static Random RANDOM = new Random();
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int target = len - k;
        int left = 0;
        int right = len - 1;
        while(true){
            int pivotIndex = partition(nums, left, right);
            if(pivotIndex == target){
                return nums[pivotIndex];
            }else if(pivotIndex < target){
                left = pivotIndex + 1;
            }else {
                right = pivotIndex - 1;
            }
        }

    }

    private int partition(int[] nums, int left, int right) {
        //随机选取pivot
        int random = RANDOM.nextInt(right - left + 1);
        swap(nums, left, left+random);
        int pivot = nums[left];
        int le = left + 1;
        int ge = right;
        while(true){
            while(le<=ge && nums[le]<pivot){
                le++;
            }
            while(le<=ge && nums[ge]>pivot){
                ge--;
            }
            if(le>=ge){
                break;
            }
            swap(nums,le, ge);
            le++;
            ge--;
        }
        swap(nums, left, ge);
        return ge;
    }

    private void swap(int[] nums, int left, int random) {
        int temp = nums[left];
        nums[left] = nums[random];
        nums[random] = temp;
    }
}

解法二：堆排序

自己实现最大堆，主要函数：建堆，调整，删除。

• 时间复杂度：O(nlog⁡n)，建堆的时间代价是 O(n)，删除的总代价是 O(klog⁡n)，因为 k<n，故渐进时间复杂为 O(n+klog⁡n)=O(nlog⁡n)。
• 空间复杂度：O(log⁡n)O(\log n)O(logn)，即递归使用栈空间的空间代价。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        buildMaxHeap(nums, heapSize);//建堆
        for(int i = 0; i < k; i++){
            swap(nums, 0, heapSize-1);
            heapSize--;
            maxHeapify(nums, 0, heapSize);//调整堆
        }
        return nums[0];
    }

    private void buildMaxHeap(int[] nums, int n) {
        //对所有非叶子节点调整
        for(int i = n/2 - 1; i >= 0; i--){
            maxHeapify(nums, i, n);
        }
    }

    private void maxHeapify(int[] nums, int i, int heapSize) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if(left < heapSize && nums[left] > nums[largest]){
            largest = left;
        }
        if(right < heapSize && nums[right] > nums[largest]){
            largest = right;
        }
        if(largest != i){
            swap(nums, largest, i);
            maxHeapify(nums, largest, heapSize);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

解法三：桶排序

注意到题目提示-10^4 <= nums[i] <= 10^4

把所有相等的元素分别放入一个桶内，从最大元素所在桶依次取出k个元素。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int[] buckets = new int[20001];
        for (int i = 0; i < nums.length; i++) {
            buckets[nums[i] + 10000]++;
        }
        for (int i = 20000; i >= 0; i--) {
            k = k - buckets[i];
            if (k <= 0) {
                return i - 10000;
            }
        }
        return 0;
    }
}