在未排序的数组中找到第 k 个最大的元素

一、引言

昨儿面试中遇到的算法题 ：在未排序的数组中找到第 k 个最大的元素。首先想到的就是先排序，但是就算是快排的时间复杂度也要O(nlogn)，给的时间有限，一时间也没想出更好的办法，想着既然时间复杂度降不下来，那不如就用简单点的堆排序：

   //大根堆 O(nlogk)
    public int findKthLargest(int[] nums, int k){
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((n1, n2) -> n1-n2);
        for (int n: nums){
            maxHeap.add(n);
            if (maxHeap.size()>k){
                maxHeap.poll();
            }
        }
        return maxHeap.poll();
    }

结果显然，面试官不是很满意，最后给的建议也是说算法有点弱，确实最近忙着实习，算法题没怎么刷，生疏了。所以趁热打铁，反思的同时，这道题的较优解还是很巧妙的，特此记录。

---

二、正文

基于快速排序的选择方法

1. 思路：

快速排序，是一个典型的分治算法
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

结合快排，对子数组进行划分，如果划分得到的值正好就是我们需要的下标，就直接返回a[q]；否则，如果 q 比目标下标小，就递归右子区间，否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间，提高了时间效率。这就是「快速选择」算法。

2. 代码：

	Random random = new Random();
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;

        // 转换一下，第 k 大元素的索引是 len - k
        int target = len - k;
        while (true) {
            //int i = random.nextInt(right - left + 1) + l;
            //swap(a, i, r);
            int index = partition(nums, left, right);
            if (index == target) {
                return nums[index];
            } else if (index < target) {
                left = index + 1;
            } else {
                right = index - 1;
            }
        }
    }
    //辅助函数，把比轴值大的元素放右边，比轴值小的元素放左边，返回轴值下标
    public int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                // 小于 pivot 的元素都被交换到前面
                j++;
                swap(nums, j, i);
            }
        }
        // 在之前遍历的过程中，满足 [left + 1, j] < pivot，并且 (j, i] >= pivot
        swap(nums, j, left);
        // 交换以后 [left, j - 1] < pivot, nums[j] = pivot, [j + 1, right] >= pivot
        return j;
    }
    
    //交换
    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

时间复杂度：O(N)，这里 N 是数组的长度，需要使用主定理进行分析。
空间复杂度：O(1)，原地排序，没有借助额外的辅助空间。
另外，为了应对极端测试用例，随机初始化 pivot 元素，随机交换第 1个元素与它后面的任意 1 个元素的位置；最极端的是顺序数组与倒序数组，此时递归树画出来是链表，时间复杂度是 O(N^2)，根本达不到减治的效果。