描述

有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。

给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。

要求：时间复杂度 O(nlogn)，空间复杂度 O(1)

思路1：大顶堆

将元素都放入大顶堆，再poll出第K个元素。空间复杂度O(n)

public class Solution {
    public int findKth(int[] a, int n, int K) {
        //大顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<>((i, j) -> j - i);
        for(int i = 0; i < n; i++) {
            queue.offer(a[i]);
        }
        for(int i = 0; i < K - 1; i++) {
            queue.poll();
        }
        return queue.poll();
    }
}

思路2：小顶堆

保证小顶堆种只有K个元素，超出K个时不断poll最小的元素。最终堆顶的元素则是第K大的元素。空间复杂度O(K)

public class Solution {
    public int findKth(int[] a, int n, int K) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i = 0; i < n; i++) {
            queue.offer(a[i]);
            if(queue.size() > K) {
                queue.poll();
            }
        }
        return queue.poll();
    }
}

思路3：快排，取第K-1个元素

快排从大到小，取排序后的第K-1个元素。（会超时）

快排写法1：以从小到大排序为例

1. index位置用于存放下一个比基准小的数，遍历将比基准小的数放到index位置
2. 遍历完成后，index左侧的数都比基准小
3. 将index-1与基准交换位置，此时基准左边的数都比基准小，基准右边的数都比基准大
4. 对基准左右两侧分别进行快排

public class Solution {
    public int findKth(int[] a, int n, int K) {
        quickSort(a, 0, n - 1);
        //取出第K大的元素
        return a[K - 1];
    }
    void quickSort(int[] a, int left, int right) {
        if(left >= right) {
            return;
        }
        int pivot = a[left];
        int index = left + 1;
        int i = index;
        while(i <= right) {
            if(a[i] >= pivot) {
                int tmp = a[i];
                a[i] = a[index];
                a[index] = tmp;
                index++;
            }
            i++;
        }
        index--;
        a[left] = a[index];
        a[index] = pivot;
        quickSort(a, left, index - 1);
        quickSort(a, index + 1, right);
    }
}

思路4：快排压缩区间

1. 假设交换后基准位置为index
2. 当K-1大于index时，说明该数在基准右侧区间，对右侧区间进行快排
3. 当K-1小于index时，说明该数在基准左侧区间，对左侧区间进行快排
4. 从大到小排序，左侧的数都比基准大，当K-1等于index时，说明第K-1个数就是基准

选择第一个元素作为基准快排会超时，需要修改基准

快排写法2：以从小到大排序为例

1. j从后往前遍历找到比基准小的数，i从前往后遍历找到比基准大的数
2. 交换i和j对应的元素
3. 当i和j相遇，交换i和基准元素，此时基准左边的数都比基准小，基准右边的数都比基准大
4. 对基准左右两侧分别进行快排

public class Solution {
    public int findKth(int[] a, int n, int K) {
        return quickSort(a, 0, n - 1, K);
    }
    int quickSort(int[] a, int left, int right, int K) {
        if(left > right) {
            return -1;
        }
        int index = partition(a, left, right);
        if(K - 1 > index) {
            return quickSort(a, index + 1, right, K);    
        } else if(K - 1 < index){
            return quickSort(a, left, index - 1, K);
        } else {
            return a[index];
        }
    }
    int partition(int[] a, int left, int right) {
        int pivot = left;
        //快排会超时，需要修改基准，这里改为left和right中间数
        swap(a, pivot, (left + right) >> 1);
        while(left < right) {
            //j找到比基准大的数，则停止
            while(left < right && a[right] <= a[pivot]) {
                right--;
            }
            //i找到比基准小的数，则停止
            while(left < right && a[left] >= a[pivot]) {
                left++;
            }
            if(left < right) {
                swap(a, left, right);
            }
        }
        swap(a, left, pivot);
        return left;
    }
    void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}