LintCode "Majority Number III"

class Solution {
    pair<int,int> majorityNumber0(vector<int> &num) {
        int count = 0;
        int ret = 0;
        for(int i = 0; i < num.size(); i ++)
        {
            if (count == 0)
            {
                ret = num[i];
                count = 1;
                continue;
            }
            if(ret != num[i]) count --;
            else if(ret == num[i]) count ++;
        }
        // find count
        int cnt = 0;
        for(auto v: num)
            if(v == ret) cnt ++;
        return make_pair(ret, cnt);
    }
public:
    /**
     * @param nums: A list of integers
     * @param k: As described
     * @return: The majority number
     */
    int majorityNumber(vector<int> nums, int k) 
    {
        int n = nums.size();
        
        auto mm = minmax_element(nums.begin(), nums.end());
        int minv = *mm.first, maxv = *mm.second;

        int dist = ((maxv - minv) / k) + 1;

        vector<pair<int, vector<int>>> bkt(k + 1, make_pair(0, vector<int>()));
        for(auto v: nums)
        {
            int inx = (v - minv) / dist;            
            bkt[inx].first ++;
            bkt[inx].second.push_back(v);
        }

        int tgt = n / k;
        for(auto &p : bkt)
        {
            if(p.first > tgt)
            {
                auto rp = majorityNumber0(p.second);
                if(rp.second > tgt)
                {
                    return rp.first;
                }
            }
        }
        return 0;
    }
};