C++ solution for elements appear more than floor(n/k) times


  • 11
    L
      vector<int> majorityElement(vector<int>& nums) {
       return majorityElement(nums, 3);
    }
    vector<int> majorityElement(vector<int>& nums, const int k) {
        const int size_n = nums.size();
        vector<int> result;
        unordered_map<int, int> cand;
        for (int i = 0; i < size_n; i++) {
            cand[nums[i]]++;
            if (cand.size() == k) {
                for (auto it = cand.begin(); it != cand.end(); ) {
                    if (--(it->second) == 0) it = cand.erase(it);
                    else it++;
                }
            }
        }
        for (auto& item : cand) item.second = 0;
        for (auto& item : nums) {
            if (cand.count(item) > 0) cand[item]++;
        }
        for (auto& item : cand) {
            if (item.second > size_n / k) result.emplace_back(item.first);
        }
        return result;
    }

  • 0
    R

    Please check the requirements carefully. O(1) space!


  • 0
    L

    I think it is O(1) space when K is 3 since 3 is a constant.


  • 0
    R

    Hi, lchen77, I think it's because of the unordered_map<int, int> cand;


  • 0
    L

    I understand your meaning. If k == 3, then unordered_map<int, int> cand will be less than 3 too. So the space is a constant space, meaning O(1).


  • 0
    R

    My mistake. You solution is correct and a nice one!


  • 0
    L

    The code is elegant and have good scalability.


  • 0
    Y
    This post is deleted!

Log in to reply
 

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