[数据结构与算法]leetcode----215.数组中的第k个最大元素（优先队列和快速选择两种解法）

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

问题：给定整数数组 nums和整数k，请返回数组中第k个最大的元素。

请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。

思路：

• 排序

这是最容易想到的思路，首先将数组排序，然后取倒数第k个就是所求。注意Arrays.sort()默认为自然排序，无法对基本数据类型的数据进行自定义排序，但是可以对其包装类Integer类型的数组自定义排序。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

• 优先队列

java的优先队列默认实现为小顶堆。将数组中的元素依次入队列，在此过程中，维护一个长度为k的队列，当队列长度大于k时，将堆顶元素（当前队列中最小的元素）出队，这样当整个数组遍历完之后，我们就留下了较大的k个元素，即堆顶为第k大元素。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();

        for(int num: nums){
            priorityQueue.offer(num);
            if(priorityQueue.size() > k){
                priorityQueue.poll();
            }
        }

        return priorityQueue.peek();
    }
}

• 快速选择算法

快速选择算法是快速排序算法的优化版本。

快速排序的逻辑是，若要对 nums[l..r] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[l..r] 都小于等于 nums[p]，且 nums[p+1..r] 都大于 nums[p]，然后递归地去 nums[l..p-1] 和 nums[p+1..r] 中寻找新的分界点，最后整个数组就被排序了。

需要优化的点在这里：每一次快排之后，分界点p的位置会被确定，我们要求的是第k大元素，这个第k大元素在升序后的数组中的位置为nums.length - k。既然我们知道了所求元素的位置，且每一次快排会确定分界点p的位置。那我们可以是用确定位置的分界点p和k作比较，若p < k，则说明第k大元素肯定在区间[p+1, r]，若p > k，则说明第k大元素肯定在区间[l, p - 1]。p == k，则nums[p]即为所求。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int l = 0, r = nums.length - 1;
        k = nums.length - k;

        while(l <= r){
            int p = partition(nums, l, r);

            if(p < k){
                l = p + 1;
            } else if(p > k){
                r = p - 1;
            } else {
                return nums[p];
            }
        }
        return -1;
    }

    private int partition(int[] nums, int l, int r) {
        if (l == r) {
            return l;
        }

        int pivot = nums[l];

        int i = l, j = r + 1;
        while (true){
            //保证nums[l...i]都小于分界点pivot
            while (nums[++i] < pivot){
                if (i == r) {
                    break;
                }
            }
			
            //保证nums[j...r]都大于分界点pivot
            while (nums[--j] > pivot){
                if (j == l) {
                    break;
                }
            }
			
            if(i >= j) {
                break;
            }
            //走到这里一定有
            //nums[i] > pivot && nums[j] < pivot
            //此时需要交换 nums[i] 和 nums[j]，
            swap(nums, i, j);
        }
        //此时i指向右半区间第一个大于pivot的数
        //j指向左半区间最后一个小于pivot的数
        //所以应该将j与分界点l交换
        //这样才满足以nums[pivot]分界点，左半区间都小于它，右半区间都大于它
        swap(nums,j,l);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

整理思路，记录博客，以便复习。若有误，望指正~