题解 | #寻找第K大#

运行时间：3ms
占用内存：544KB

使用最大堆解决 第 TopK 问题

class Solution {
public:
    // 第 K 大使用最大堆
    void MAX_HEAPIFY(std::vector<int> &arr, int begin, int end) {
        int l       = begin * 2 + 1;
        int r       = begin * 2 + 2;
        int largest = begin;
        if(l <= end && arr[l] > arr[largest]) largest = l;
        if(r <= end && arr[r] > arr[largest]) largest = r;
        if(largest != begin) {
            std::swap(arr[begin], arr[largest]);
            MAX_HEAPIFY(arr, largest, end);
        }
    }
    int findKth(vector<int> a, int n, int K) {
        // 构建堆
        for(int i = a.size() / 2 - 1; i >= 0; --i) MAX_HEAPIFY(a, i, a.size() - 1);
        for(;K>1;--K){
            a[0] = a[a.size() - 1];
            a.pop_back();
            MAX_HEAPIFY(a, 0, a.size() - 1);
        }
        return a[0];
    }
};

这个算法算是我刷题到现在写的最长的一个了。。。总是细节出问题，气的我甚至用 gtest 本地一个一个函数过的。

一次是 MAX_HEAPIFY(a, i, a.size() - 1) 中的 i 写成了 0，结果导致建堆没建完整

一次是 a[0] = a[a.size() - 1] 写的 a[0] = *a.end() 。结果卡在了第 19 个测试上

一次是 K>1 写成了 K>0 ，卡在了第 14 个测试上

不过看到它 ac 100% 还是很开心。尽管内存占用有些大。。。但是没有用标准库中的 sort 和 make_heap。算是没有投机取巧