【leetcode】703. 数据流中的第 K 大元素（kth-largest-element-in-a-stream）（模拟）[简单]

链接

https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/

耗时

解题：1 h 25 min
题解：26 min

题意

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

• KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
• int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

思路

建立（降序排序后）前 k 大元素的小顶堆，这样堆顶即是第 k 大元素，每次 add 更新数据流时，如果 val <= 堆顶元素 则无需处理，因为加入的 val 不会改变前 k 大元素的的任意一个，第 k 大元素还是堆顶元素；而如果 val > 堆顶元素 则加入的 val 必然会改变前 k 大元素，当前堆顶的元素不再有用，它将变成第 k+1 大的元素，所以将堆顶元素的值直接改成 val，并调整小顶堆，这样堆顶就重新变成第 k 大元素。

时间复杂度： O ( m a x ( a d d n u m ∗ l o g k , n l o g n ) ) O(max(addnum*logk, nlogn)) O(max(addnum∗logk,nlogn))

AC代码

class KthLargest {
private:
    vector<int> arr;
    int k;
public:
    // 小顶堆
    void heapAdjust(vector<int>& arr, int l, int r) { // 只有堆顶位置不对，调整他
        int dad = l;
        int son = dad * 2 + 1;
        while (son <= r) { // 若子節點指標在範圍內才做比較
            if (son + 1 <= r && arr[son] > arr[son + 1]) // 先比較兩個子節點大小，選擇最小的
                son++;
            if (arr[dad] < arr[son]) // 如果父節點小於子節點代表調整完畢，直接跳出函數
                return;
            else { // 否則交換父子內容再繼續子節點和孫節點比較
                swap(arr[dad], arr[son]);
                dad = son;
                son = dad * 2 + 1;
            }
        }
    }
    
    KthLargest(int k, vector<int>& nums) {
        this->arr = nums;
        sort(arr.begin(), arr.end(), greater<int>());
        this->k = k;
        if(arr.size() >= k) {
            for (int i = k/2-1; i >= 0; --i) { // 从第一个非叶子结点开始 
                heapAdjust(arr, i, k-1);
            }
        }
    }
    
    int add(int val) {
        if(arr.size() < k) {
            arr.push_back(val);
            for (int i = k/2-1; i >= 0; --i) { // 从第一个非叶子结点开始 
                heapAdjust(arr, i, k-1);
            }
        }
        else {
            if(val > arr[0]) {
                arr[0] = val;
                heapAdjust(arr, 0, k-1);
            }
        }
        return arr[0];
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */