Majority Element using priority_queue


  • 0
    Z

    I try using priority_queue to solve the problem, build heap takes O(n),pop[n/2] times takes O(2logn)n/2,
    so this solution should takes O(n
    logn), but it takes longer than I assumed, which is 73ms.
    my code:

    #include <algorithm>
    #include <vector>
    using std::vector;
    #include <queue>
    using std::priority_queue;
    
    class Solution {
    public:
        int majorityElement(vector<int> &num) {
            priority_queue<int> p(num.begin(),num.end());
            size_t limit= num.size()/2;
            for(size_t i=0; i< limit;++i) {
                p.pop();
            }
            return p.top();
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.