leetcode 295. 数据流的中位数：自定义仿函数比less＜int＞ greater＜int＞慢？

忘是亡心i 2023-01-22 07:53 38阅读 0赞

思路就不说了 请参考  
[https://leetcode-cn.com/problems/find-median-from-data-stream/solution/shu-ju-liu-de-zhong-wei-shu-by-leetcode/][https_leetcode-cn.com_problems_find-median-from-data-stream_solution_shu-ju-liu-de-zhong-wei-shu-by-leetcode]

只是为啥我自己定义的仿函数就慢了呢？

#define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    class MedianFinder { 
    public:
        /** initialize your data structure here. */
        
        priority_queue<int,vector<int>,less<int>> maxq;
        priority_queue<int,vector<int>,greater<int>> minq;
        
        MedianFinder() { 
            
        }
        
        void addNum(int num) { 
            if(!maxq.empty() && num<=maxq.top()){ 
                maxq.push(num); 
            }else{ 
                minq.push(num);
            }
            
            if(maxq.size() > minq.size()+1){ 
                minq.push(maxq.top());
                maxq.pop();
            }else if(minq.size() > maxq.size()+1){ 
                maxq.push(minq.top());
                minq.pop();
            }
        }
        
        double findMedian() { 
            
            if(maxq.size() == minq.size()){ 
                return ((double)maxq.top()+(double)minq.top())/2;
            }else{ 
                return maxq.size() > minq.size()?(double)maxq.top():(double)minq.top(); 
            }
            return 0;
        }
    };
    
    /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */

![在这里插入图片描述][20210518220526917.png]

#define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    class MedianFinder { 
    public:
        /** initialize your data structure here. */
        
        struct cmp1{ 
            bool operator () (int a,int b){ 
                return a < b;
            }  
        };
        
        struct cmp2{ 
            bool operator () (int a,int b){ 
                return a > b;
            }  
        };
        
        priority_queue<int,vector<int>,cmp1> maxq;
        priority_queue<int,vector<int>,cmp2> minq;
        
        MedianFinder() { 
            
        }
        
        void addNum(int num) { 
            if(!maxq.empty() && num<=maxq.top()){ 
                maxq.push(num); 
            }else{ 
                minq.push(num);
            }
            
            if(maxq.size() > minq.size()+1){ 
                minq.push(maxq.top());
                maxq.pop();
            }else if(minq.size() > maxq.size()+1){ 
                maxq.push(minq.top());
                minq.pop();
            }
        }
        
        double findMedian() { 
            
            if(maxq.size() == minq.size()){ 
                return ((double)maxq.top()+(double)minq.top())/2;
            }else{ 
                return maxq.size() > minq.size()?(double)maxq.top():(double)minq.top(); 
            }
            return 0;
        }
    };

![在这里插入图片描述][20210518220638555.png]

[https_leetcode-cn.com_problems_find-median-from-data-stream_solution_shu-ju-liu-de-zhong-wei-shu-by-leetcode]: https://leetcode-cn.com/problems/find-median-from-data-stream/solution/shu-ju-liu-de-zhong-wei-shu-by-leetcode/
[20210518220526917.png]: /images/20221020/4e8fd953367b433490b187edefcf52d2.png
[20210518220638555.png]: /images/20221020/d720651b3711443d905174fcfdd8e4af.png