Short 20ms linear time C++ solution


  • 8
    D
    class Solution {
    public:
        int majorityElement(vector<int> &num) {
            int cand = 0, count = 0;
            for (int i = 0; i < num.size(); ++i) {
                if (count == 0) {
                    cand = num[i];
                    count = 1;
                } else if (num[i] == cand) {
                    count++;
                } else {
                    count--;
                }
            }
            return cand;
        }
    };

  • 0
    A

    HI, sorry I don't get it. Why can it solve the problem


  • 0
    I

    You can assume that there are two "number" in the vector. One is the majority number, the other one is the rest of the vector.


  • 0
    A

    This is a very clear solution. Thanks for sharing.
    I am confused why it still takes 20ms to run it...


Log in to reply
 

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