215. 数组中的第K个最大元素

思路：
用堆很简单，我就不多说了：

public int findKthLargest(int[] nums, int k) {
    // init heap 'the smallest element first'（小顶堆）
    PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        //new PriorityQueue<Integer>((n1, n2) -> n1 - n2);
    for (int n: nums) {
      heap.add(n);
      if (heap.size() > k)
        heap.poll();
    }
    return heap.poll();        
}

另一种思路是快速排序。也就是我们每次随机选一个分割点，然后把小于该点的数放在左边，大于该点的数放在右边，然后对比此时分割点的索引和 nums.length - k 是否相等，如果相等直接返回该数；如果索引大于 nums.length - k 则往分割点左边再找一个分割点重复相同操作；如果索引小于 nums.length - k 则往分割点右边再找一个分割点重复相同操作。

    public int findKthLargest(int[] nums, int k) {
        // 要找到的元素所在索引:  前K大，即倒数索引第K个
        int index = nums.length - k;
        int right = nums.length - 1;
        int left = 0;
        return quickSelect(nums, left, right, index);
    }
    public int quickSelect(int[] nums, int left, int right, int index) {
        // 得到分区值索引q
        int q = randomPartition(nums, left, right);
        if (q == index) {
            // 如果刚好索引q就是想要的索引，则直接返回
            return nums[q];
        } else {
            // 如果不是，比较q 与 index ,确定下次要检索的区间, 要么是[q+1, right], 要么就是[left, q-1]
            return q < index ? quickSelect(nums, q + 1, right, index) : quickSelect(nums, left, q - 1, index);
        }
    }

那么我们如何选取分割点呢，我们可以随机选取：

    Random random = new Random();
    public int randomPartition(int[] nums, int l, int r) {
        // 1. 随机数范围: [0, r-l+1) 同时加l, 则是 [l, r+1) = [l, r] 也就是在这个[l,r] 中随机选一个索引出来
        int i = random.nextInt(r - l + 1) + l;
        // 2. 交换nums[i]， nums[r], 也就是将随机数先放在[l,r]最右边nums[r]上
        swap(nums, i, r);
        return partition(nums, l, r);
    }

选完分割点后开始将l和r间的数分成两份，我们先把分割点放在数组右端，然后开始遍历数组，从左往右遍历，遇到比分割点小的数就换到前面去，遍历完后把分割点插入中间（与中间的i+1交换）：

    public int partition(int[] nums, int l, int r) {
        // 3. 在调用当前方法的randomPartition方法中，已经确定了了随机数是nums[r]
        int x = nums[r], i = l - 1;
        // 首先比较区间在[l， r]之间， 所以nums[j]中的    l<= j <= r
        for (int j = l; j < r; ++j) {
            // 4. nums[j] 跟随机数 x 比较, 小于x的数都跟[l,r]左边区间交换，i=l-1,所以++i=l,初始索引就是l,
            if (nums[j] <= x) {
                swap(nums, ++i, j);//两两交换
            }
        }// 这个for循环操作就是将小于 x 的数都往[i, j]的左边区间设置，从而实现存在[l, i]区间,使得对应数值都 小于 x
        //5. 既然已经将<x的值都放在一边了，现在将x也就是nums[r] 跟nums[i+1]交换，从而分成两个区间[l.i+1]左, [i+2, r]右，左边区间的值都小于x
        swap(nums, i + 1, r);
        // 然后返回这个分区值
        return i + 1;
    }

完整代码如下：

    Random random = new Random();
    public int findKthLargest(int[] nums, int k) {
        // 要找到的元素所在索引:  前K大，即倒数索引第K个
        int index = nums.length - k;
        int right = nums.length - 1;
        int left = 0;
        return quickSelect(nums, left, right, index);
    }
    public int quickSelect(int[] nums, int left, int right, int index) {
        int q = randomPartition(nums, left, right);// 得到分区值索引q
        if (q == index) {
            return nums[q];
        } else {
            return q < index ? quickSelect(nums, q + 1, right, index) : quickSelect(nums, left, q - 1, index);
        }
    }
    public int randomPartition(int[] nums, int l, int r) {
        int i = random.nextInt(r - l + 1) + l;
        swap(nums, i, r);
        return partition(nums, l, r);
    }
    public int partition(int[] nums, int l, int r) {
        int x = nums[r], i = l - 1;
        for (int j = l; j < r; ++j) {
            if (nums[j] <= x) {
                swap(nums, ++i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }
    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }