Moore Voting, Sorting and Bit Counting solutions in C++


  • 0

    Moore Voting Algorithm

    class Solution {
    public:
        int majorityElement(vector<int>& nums) 
        {
            int a = nums[0]-1, count = 0;
            for(int i = 0; i < nums.size(); ++i)
            {
                if(count==0 || a==nums[i]) count++, a = nums[i];
                else count--;
            }
            return a;
        }
    };
    

    Sorting

    class Solution {
    public:
        int majorityElement(vector<int>& nums) 
        {
            sort(nums.begin(), nums.end());
            return nums[nums.size()/2];
        }
    };
    

    Bit Counting

    class Solution {
    public:
        int majorityElement(vector<int>& nums) 
        {
            int len = sizeof(int)*8, size = nums.size();
            int count = 0, mask = 1, ret = 0;
            for(int i = 0; i < len; ++i)
            {
                count = 0;
                for(int j = 0; j < size; ++j)
                    if(mask & nums[j]) count++;
                if(count > size/2) ret |= mask;
                mask <<= 1;
            }
            return ret;
        }
    };
    

Log in to reply
 

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