C++ 3 simple solutions


  • 12
    Z
    class Solution {
    public:
    int majorityElement(vector<int>& nums) {
        //return solution1(nums);     //use map
        //return solution2(nums);     //use sort
        return solution3(nums);     //use O(1) space
    }
    private:
    int solution1(vector<int> &nums){
        unordered_map<int, int> m;
        for(int i = 0; i < nums.size(); i++)
            m[nums[i]]++;
        auto cur = m.begin();
        for(auto i = cur; i != m.end(); i++){
            if(cur->second < i->second) cur = i;
        }
        return cur->first;
    }
    int solution2(vector<int> &nums){
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
    int solution3(vector<int> &nums){
        int cur = nums[0];
        for(int i = 1, count = 1; i < nums.size(); i++){
            if(nums[i] == cur) count++;
            else count--;
            if(count == -1){
                cur = nums[i];
                count = 1;
            }
        }
        return cur;
    }
    };

  • 0
    D

    sol2 is pretty neat!!


  • 0
    Z

    yeah, but it is definitely not the answer hiring managers will expect.


  • 0
    D

    i see, so probably sol3 is more favorable


  • 0
    Z

    yea, but I think solution 1 is more straightforward if the question allows using extra space.


Log in to reply
 

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