第k大数字

找第k大数字三种解决方法：
1.暴力，选择/冒泡，这里以冒泡为例；时O(n^2)，空O(1)

public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        for (int i = 0; i < k; i ++) {
            for (int j = 0; j < n - i - 1; j ++) {
                if(nums[j] > nums[j + 1]) {
                    int t = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = t;
                }
            }
        }
        return nums[n - k];
    }

2.优先队列时；O(n)，空O(n)

public int findKthLargest(int[] nums, int k) {
        PriorityQueue pq = new PriorityQueue<>(new Comparator() {
            public int compare(Integer i1, Integer i2) {
                return i2 - i1;
            }
        });
        int n = nums.length;
        for(int i = 0; i < n; i ++) pq.add(nums[i]);
        for(int i = 0; i < k - 1; i ++) pq.poll();
        return pq.poll();
    }

3.快排/快速选择算法；时O(n)，空O(1)

public int quick_sort(int[] nums, int k, int l, int r) {
        if(l >= r) return nums[l];

        int i = l - 1, j = r + 1, mid = nums[l + r >> 1];
        while(i < j) {
            while(nums[++ i] > mid);
            while(nums[-- j] < mid);
            if(i < j) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }

        int sl = j - l + 1;
        if(sl < k) return quick_sort(nums, k - sl,  j + 1, r);
        return quick_sort(nums, k, l, j);
    }
    public int findKthLargest(int[] nums, int k) {
        return quick_sort(nums, k, 0, nums.length - 1);
    }