C++ different solutions.


  • 11
    C
    int majorityElement1(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size()/2];
    }
    
    int majorityElement2(vector<int>& nums) {
        //unordered_map<int, int> myMap;
        map<int, int> myMap;
        for (auto& num: nums) {
            myMap[num]++;
            if (myMap[num]>nums.size()/2)
                return num;
        }
    }
    
    int majorityElement3(vector<int>& nums) {
        //multimap<int, int> myMap;
        unordered_multimap<int, int> myMap;
        for (auto& num: nums) {
            if (myMap.find(num) == myMap.end())
                myMap.insert(make_pair(num, 1));
            else {
                int tmp = (*myMap.find(num)).second+1;
                myMap.erase(num);
                myMap.insert(pair<int, int>(num, tmp));
            }
            if (myMap.find(num)->second > nums.size()/2)
                return num;
        }
    }
    
    int majorityElement4(vector<int>& nums) {
        int bit[32] = {0};
        for (auto& num: nums) 
            for(int i=0; i<32; i++) 
                if ((num>>i)&1 == 1)
                    bit[i]++;
        int ret = 0;
        for (int i=0; i<32; i++) {
            ret+=(1<<i)*(bit[i]>nums.size()/2?1:0);
        }
        return ret;
    }
    
    int majorityElement(vector<int>& nums) {
        int count=0, ret=0;
        for (auto& num: nums) {
            if (count == 0)
                ret = num;
            if (num != ret)
                count--;
            else
                count++;
        }
        return ret;
    }

Log in to reply
 

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