Skip to content

Latest commit

 

History

History
276 lines (202 loc) · 6.5 KB

堆.md

File metadata and controls

276 lines (202 loc) · 6.5 KB

堆总结

合并K个排序链表

LeetCode中文

LeetCode英文

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

解答

要对k个链表进行合并排序，可以维护一个最小堆。步骤如下：

  1. 首先将每个非空链表的表头加入最小堆；
  2. 每次弹出一个堆顶元素作为链表的下一个节点，如果此时堆顶元素的下一个节点非空，将它加入最小堆；
  3. 重复步骤2，直到最小堆为空。

注意：最小堆的元素类型是链表节点指针ListNode*不是ListNode。

假设所有链表的节点总数为n

  • 时间复杂度O(n log k)
  • 空间复杂度O(k)

方法1

使用优先级队列priority_queue

priority_queue的接口使用可以参考C++ Primer第五版 或者 STL源码剖析

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    static bool comp(ListNode* p1,ListNode* p2)
    {
        return p1->val > p2->val;
    }
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,decltype(comp)*> que(comp);
        
        for(auto p : lists)
        {
            if(p) que.push(p);
        }  
        
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        while(!que.empty())
        {
            auto tmp = que.top();
            que.pop();
            
            if(tmp->next) que.push(tmp->next);
            
            cur->next = tmp;
            cur = cur->next;
        }
        
        return dummy->next;
        
    }
};

方法2

使用堆heap的接口函数make_heap、push_heap和pop_heap。

heap接口的使用参考STL源码剖析

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

inline bool comp(const ListNode* p1,const ListNode* p2)
{
    return p1->val > p2->val;
}

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty())
            return nullptr;
        
        vector<ListNode*> min;
        for(auto p : lists)
        {
            if(p) min.push_back(p);
        }
        
        make_heap(min.begin(),min.end(),comp);
        
        ListNode head(0);
        ListNode* tail = &head;
        while(!min.empty())
        {
            auto cur = min.front();
            pop_heap(min.begin(),min.end(),comp);
            min.pop_back();
            
            tail->next = cur;
            tail = cur;
            
            if(cur->next)
            {
                min.push_back(cur->next);
                push_heap(min.begin(),min.end(),comp);
            }
        }
        
        return head.next;
    }
};

数据流的中位数

LeetCode中文

LeetCode英文

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

示例：

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

进阶:

  • 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
  • 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

解答

维护一个最大堆max和最小堆min，保持max的堆顶元素不大于min的堆顶元素，同时两个堆的元素个数相差不超过1。

对于数据流中的每个数num，函数addNum处理情况如下：

  1. 如果num > max.top()，则num加入最大堆max；
  2. 如果num <= min.top()，则num加入最小堆min；

同时比较max和min的元素个数，处理情况如下：

  1. 如果max.size() - min.size() > 1，则从max弹出堆顶元素并加入min；
  2. 如果min.size() - max.size() > 1，则从min弹出堆顶元素并加入max；

取得中位数，函数findMedian处理情况如下：

  1. 如果max.size() == min.size()，则中位数是min和max的堆顶元素取中值；
  2. 如果max.size() > min.size()，则中位数是max的堆顶元素；
  3. 如果min.size() > max.size()，则中位数是min的堆顶元素；

假设目前的元素个数为n，那么

  • 时间复杂度：addNum为O(log n),findMedian为O(1)
  • 空间复杂度：O(n)
class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        if(max.empty())
            max.push(num);
        else{
            if(num > max.top())
                min.push(num);
            else
                max.push(num);
        }
        
        int len_max = max.size();
        int len_min = min.size();
        if(len_max - len_min > 1)
        {
            int a = max.top();
            max.pop();
            
            min.push(a);
        }
        else if(len_min - len_max > 1)
        {
            int a = min.top();
            min.pop();
            
            max.push(a);
        }
    }
    
    double findMedian() {
        int len1 = max.size();
        int len2 = min.size();
        double res;
        if(len1 == len2)
        {
            res = static_cast<double>(((double)(max.top()) + (double)(min.top()))/2.0);
        }
        else if(len1 > len2){
            res = (double)(max.top());
        }
        else 
            res = (double)(min.top());
        
        return res;
    }
    
priority_queue<int> max;
priority_queue<int,vector<int>,greater<int>> min;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */