55.Kth Largest Element in an Array-数组中的第K个最大元素

解析：方法1：优先级队列， 方法2：快速排序

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //方法1：优先级队列(堆排序)
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int num : nums) {
            queue.add(num);
        }
        for (int i = 0; i < k - 1; i++) {
            queue.remove();
        }
        return queue.remove();
    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //方法2：快速排序(随机找基准，当基准正好落在k-1的位置上时，该基准就是所求)
        while (true) {
            int[] index = partition(nums, 0, nums.length - 1);
            if (index[0] <= nums.length - k && nums.length - k <= index[1]) {
                return nums[index[0]];
            }
        }
    }
    private int[] partition(int[] arr, int start, int end) {
        int target = arr[new Random().nextInt(end+1)]; //指定一个数，将数组变成    
                                              //<target =target >target  三部分
        int less = -1, more = end + 1, p = 0;
        while (p < more) {
            if (arr[p] > target) {
                swap(arr, p, --more);
            } else if (arr[p] < target) {
                swap(arr, ++less, p++);
            } else {
                p++;
            }
        }
        return new int[]{less + 1, more - 1};
    }
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}