C++ simple and short


  • -1
    X
    class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) {
            return majorityElementGenelized(nums, 3);
        }
    private:
        vector<int> majorityElementGenelized(vector<int>& nums, int k){
            if(k <= 1 || nums.empty()){
                return vector<int>{};
            }
            int n = nums.size();
            vector<int> candidate(k, nums[0]);
            vector<int> count(k, 0);
            count[0] = 1;
            for(int i = 1; i < n; ++i){
                auto p = find(candidate.begin(), candidate.end(), nums[i]);
                if(p != candidate.end()){
                    ++count[p - candidate.begin()];
                }else{
                    auto p = find(count.begin(), count.end(), 0);
                    if(p != count.end()){
                        count[p - count.begin()] = 1;
                        candidate[p - count.begin()] = nums[i];
                    }else{
                        for_each(count.begin(), count.end(), [](int& x){--x;});
                    }
                }
            }
            int r = n / k;
            vector<int> ans;
            for(int i = 0; i < k; ++i){
                if(count[i] > 0 && std::count(nums.begin(), nums.end(), candidate[i]) > r){
                    ans.push_back(candidate[i]);
                }
            }
            return ans;
        }
    };

Log in to reply
 

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