题目

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

思路

1. 对数组排序，取索引值为k-1处的值。
   时间复杂度是排序算法的时间复杂度：O(nlogn)
   虽然这个解法是正确的，但还可以继续优化：我们只需返回第K大的数，没必要对整个数组排序。
2. 利用快排Partition思想
   Partition后，会把选取的枢纽元素放在排序后的正确位置，其左边是比其大的元素，其右边是比pivot值小的元素。
   假设此时枢纽元素位于索引X处：若K>X+1，继续在X右边查找；若K<X+1，继续在X左边查找。
   直到K==X+1 ，此时找到nums数组中第K大的数：nums[K-1]。

Java实现

class Solution {
public int findKthLargest(int[] nums, int k) {

        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            int j = partition(nums, lo, hi);
            if(j+1 < k) 
                lo = j + 1 ;
             else if (j+1 > k) 
                hi = j - 1;
             else 
                break;
            
        }
        return nums[k-1];
    }



    private void exch(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }


    private int partition(int nums[] , int l, int r){

            int j=l;
            int v = nums[l];
            for(int i=l+1;i<=r;i++){
                if(nums[i]>v)
                    exch(nums,++j,i);
            }
            exch(nums,l,j);
        
            return j;

    } 
}

3. 利用最小堆
   后面再补