C++ solution with explanation, O(n) time and O(1) space


  • 12
    A

    We can apply the same idea as easy version of majority element. If we remove three elements with different value at the same time, finally we should filter out the majority elements. So in the first pass, we search for possible majority elements (the number of majority element <3), and then for each candidate, we scan the array again to confirm wether it's majority or not.

    Updated
    Some guys are confused by the first branch, i.e.

     if(nums[i] == candidate1) count1 ++;
    

    Here we don't need to verify the value of count1. Why? Because if count1 is 0, and nums[i] = candidate1,
    we can still just add one to count1. It's logically safe.


    class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) {
            int array_size = nums.size();
            int candidate1, candidate2;
            int count1 = 0;
            int count2 = 0;
            for(int i = 0; i < array_size; i ++){
                if(nums[i] == candidate1) count1 ++;
                else if(nums[i] == candidate2) count2 ++;
                else{
                    if(count1 && count2) {count1 --; count2 --;}
                    else if (count1){candidate2 = nums[i]; count2 = 1;}
                    else {candidate1 = nums[i]; count1 = 1;}
                }
            }
            vector<int> candidate;
            if(count1 > 0) candidate.push_back(candidate1);
            if(count2 > 0) candidate.push_back(candidate2);
            vector<int> result;
            for(int i = 0; i < candidate.size(); i ++){
                int count = 0;
                for(int j = 0; j < array_size; j ++){
                    if(nums[j] == candidate[i]) count ++;
                }
                if(count > array_size/3) result.push_back(candidate[i]);
            }
            return result;
        }
    };

  • 0
    L

    In your code, candidate1 and candidate2 are uninitialized, but they are used in comparison. Your program can be more robust if it's fixed.


  • 0
    A

    Thanks for your reminder. It's safe here since that candidate1&2 would only be used if the count > 0, which would ensure that the variables are initialized.


  • 0
    P

    not sure what you mean, uninitialized use here :

       for(int i = 0; i < array_size; i ++){
            if(nums[i] == candidate1) count1 ++;

  • 0
    A

    Hi Pavel10,
    Considering we only need to make sure that the counter is correct, we can have any initialized value for candidate. Then I think it's not necessary to initialize it. Correct me if there is still any mistake. I remember there is a default value for uninitialized variable.


  • 0
    V

    No there is no default value. For msvc, 0xcdcdcdcd is the default value for debug mode. However it's not true for release mode.


  • 1
    R

    Nice Solution.
    That's the key:
    "If we remove three elements with different value at the same time, finally we should filter out the majority elements."

    But I think Louis.Howard is right. nums[i] == candidate1 is the first expression to evaluation. Maybe you can change the structure of if--else to make sure this comparison used when count > 0. Or make it count1&&nums[i] == candidate1


  • 4

    Hi, alfred.yu. Thank you for your code and explanations. It is awesome!

    I have rewritten it below.

    class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) {
            int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;
            for (int num : nums) {
                if (num == candidate1) count1++;
                else if (num == candidate2) count2++;
                else {
                    if (!count1) {
                        candidate1 = num;
                        count1++; 
                    }
                    else if (!count2) {
                        candidate2 = num;
                        count2++;
                    }
                    else { 
                        count1--;
                        count2--;
                    }
                }
            }
            count1 = count2 = 0;
            for (int num : nums) {
                if (num == candidate1) count1++;
                else if (num == candidate2) count2++;
            }
            int n = nums.size();
            vector<int> majority;
            if (count1 > n / 3) majority.push_back(candidate1);
            if (count2 > n / 3) majority.push_back(candidate2);
            return majority;
        }
    };

  • 0
    A

    hi ragepyre, I have added some explanation in original question (updated session). Correct me if I am wrong.


  • 0
    R

    Thank you for the explaination. Now I got it


Log in to reply
 

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