NC88 寻找第K大

1. 笨办法

既然是找第k大的数, 那就排序返回第k-1号元素就好了~~~

这里需要注意, 是递减排序

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        sort(a.begin(), a.end(), greater<int>());
        return a[K-1];
    }
};

时间复杂度: O(nlogn), 很标准的排序算法复杂度.
空间复杂度: O(1). 无额外空间

2. 基于堆排序

先复习一下堆的概念:

堆中某个结点的值总是不大于或不小于其父结点的值；
堆总是一棵完全二叉树。

父节点元素大于等于子节点的, 叫大根堆, 否则叫小根堆.

一个堆的示例如图所示：图片说明

计算机中，我们使用数组模拟的完全二叉树来模拟堆，上图的大根堆可以存储如下：

图片说明

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

这道题建一个大小为k的小根堆, 遍历数组, 如果堆不满, 则入堆, 否则做如下判断:

如果堆顶元素大于等于当前元素, 说明这个数一定不会是第k大的, 原因很简单, 堆里面已经有k个数, 且都大于等于堆顶的那个, 因此丢弃;
如果堆顶元素小于当前元素, 去掉堆顶元素, 再把当前元素入堆

最后堆顶元素即为所求. 在C++中, 我们有priority_queue, Java中有PriorityQueue等封装好的类, 为了更具有一般性, 本题使用手写的小根堆. 为了便于实现，本题中的堆下标从1开始存储，这样节点i的左孩子和右孩子可以更简单地表达为i<<1和i<<1|1。

class Solution {
public:
    int *heap;
    int size = 0; // 初始化堆中元素个数为0
    
    int findKth(vector<int> a, int n, int K) {
        heap = new int[K+5];
        for (auto i : a) {
            // 堆没满, 继续往堆里面放元素
            if (size < K) {
                add(i);
            } else if (i > top()){
                pop(); 
                add(i);
            }
        }
        
        return top();
    }

    // 增加一个元素
    void add(int u) {
        heap[++size] = u;
        up(size); // 加到尾巴了, 需要向上调整
    }
    
    // 堆顶元素
    int top() {
        return heap[1];
    }
    
    void pop() {
        heap[1] = heap[size--];
        down(1); //向下调整
    }
    
    void up(int u) {
        // 定义当前节点为cur, 父节点为f
        int f = u / 2, cur = u;
        // 如果有父节点且父节点更大, 说明需要往上调
        while (f && heap[f] > heap[cur]){
            swap(heap[f], heap[cur]);
            up(f); // f也可能需要上调, 递归
        }
    }
    
    void down(int u) {
        // 定义u的左右儿子分别是lson和rson
        int lson = u << 1, rson = u << 1 | 1;
        
        // t表示父节点、左儿子、右儿子里面最小值的下标
        int t = u;
        // 如果左儿子未越界, 且更小, 则t=lson
        if (lson <= size && heap[lson] < heap[t])
            t = lson;
        // 同上, 如果是大根堆这里就换一下
        if (rson <= size && heap[rson] < heap[t] )
            t = rson;
        // 如果u不是t，说明三者中最小的是某个子节点，那就和最小的交换一下
        if (u != t) {
            swap(heap[u],heap[t]);
            down(t); // 换过来之后的t, 有可能还需要继续向下
        }
    }
};

时间复杂度: O(nlogK), 调整堆的复杂度为logK, 且循环n轮.
空间复杂度: O(K). 开了一个大小为K的数组, 代表堆

3. 基于快速排序(分治算法)

本题跟快速排序差不多, 具有子问题的性质, 所以我们可以魔改快排的思路, 先取最左元素为中轴, 进行一轮从大到小的快排, 如果:

排序之后, 中轴元素恰好排到了第k名: 那么恭喜,中轴元素就是答案
如果中轴元素下标>k: 说明答案在左半边, 递归.
否则, 答案在右半边.

快速排序的思路可以参考这道题: 拼接所有的字符串产生字典序最小的字符串

据此可以这样实现: 设问题范围为kthElement(arr, l, r, k), 代表arr数组, 范围为[l, r]中找第k大的元素. 那么最终的问题是求kthElement(arr, 0, n-1, k). 每一轮快排后, 设中轴排到了第m位, 则判断:

m == k, 那么arr[m]即为答案
m > k, 那么答案在左边, 问题转化为求kthElement(arr, l, m-1, k)
m < k, 那么相当于求kthElement(arr, m+1, r, k)

这里实现的时候有一个细节需要注意: 题目中的k是从1开始, 数组下标是从0开始, 因此代码中的k要用k-1代替.

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        return quick_sort(a, 0, n-1, K);
    }
    
    int quick_sort(vector<int> &a, int start, int end, int k) {
        int i = start, j = end; // 左右端点
        int p = a[i]; // 取最左元素为中轴
        
        while (i < j) {
            // 右边的数字如果大于等于基准, 则j指针往左走
            while (i < j && p >= a[j]) j--;
            // j走到严格小于基准的数, 把i换过去
            a[i] = a[j];
            
            // 同理
            while (i < j && p <= a[i]) i++;
            a[j] = a[i];
        }
        
        // ij相遇, 赋值为中轴元素
        a[i] = p;
        if (i == k-1) return a[i];
        else if (i > k-1) return quick_sort(a, start, i-1, k);
        else return quick_sort(a, i+1, end, k);
    }
};

时间复杂度: 平均复杂度 O(n). 这个跟快排的区别是, 快排需要递归两边, 而本题只需要递归一边. 平均而言, 每次问题规模缩小一半, 相当于计算量是:

n+n/2+n/4..... = 2n

但是如果数据比较极端，在完全倒序的情况下，每次递归一边的时候问题规模只减小1，相当于计算量是：

n+(n-1)+(n-2)+....+1 = n*(n+1)/2

因此，最差的时间复杂度为O(n2).

空间复杂度: 平均空间复杂度O(logn)，最坏空间复杂度O(n). 对于每一次函数调用，均为常数空间, 观察上式，平均情况下整个算法递归logn次，最坏递归n次，故可以得出空间复杂度。

题解 | #寻找第K大#

NC88 寻找第K大

1. 笨办法

2. 基于堆排序

3. 基于快速排序(分治算法)