题目

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

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

解题思路

快速选择：快速排序的分区算法,平均时间复杂度为O(n),第k大可以倒序分区。
哈希：使用数组哈希,也只会有一重循环遍历。

快速选择

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //快速选择partition:快速排序的分区思想，快排的思想是一次找出一个数的正确位置，
        // 并使得该数左边的元素都比它小，该数右边的元素都比它大，要找出第k
        // 大的元素，只需要在快排的时候采用降序排序，找到下标为k-1的元素。
        return quickSelect(0,nums.length-1,nums,k);//或者升序排序返回nums[n-k]
    }
    Random random = new Random();
    int quickSelect(int start,int end,int[] nums,int k) {
        //随机选一个数作为数轴 加速查找
        int rand = start+random.nextInt(end-start+1), base = nums[rand];
        swap(start,rand,nums);//放在开头位置
        int index = start;
        // 剩下元素依次与base比较，倒序排序,大的放前面
        //3,2,1,5,6,4, k=2 :        1 5 6 4 3 2 
        for (int i = start + 1; i <= end; i++) {
            if (nums[i] > base) swap(++index,i,nums);
            //if (nums[i] >= base && ++index != i) swap(index,i,nums);
        }
        // base存放在区间开头，现在需要把它交换到index位置，即它在整个有序数组中的位置。
        swap(index, start, nums);
        // 如果index等于k-1已找到 小于k-1在右边区间查找,否则在左边
        if(index == k-1) return nums[index];
        else if (index < k-1) return quickSelect(index + 1, end, nums, k);
        else return quickSelect(start, index - 1, nums, k);
    }

    void swap(int a,int b,int[] nums) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

复杂度分析

时间复杂度：O(n)，使用了随机化后规避了快速选择的特殊情况的最坏时间复杂度,平均时间复杂度O(n)。
空间复杂度：O(n)，递归栈空间,也可以使用"二分查找式循环"优化空间到O(1)。

哈希

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //哈希计数
        int[] hash = new int[20001];
        for(int i : nums) hash[i+10000]++;
        int count = 0;
        for(int i = hash.length-1,size = hash[i]; i >= 0; i--,size = hash[i]) {
            while(size > 0) {
                size --;
                if(++count == k) return i-10000;
            }
        }
        return -1;
    }
}