My O(N) solution


  • 12
    L

    I think this is one of the classical selection problem. The idea is simple, each time, pick any two elements, if they're different, then, remove both of them. As the majority element appears more than n/2 times, when the whole array is scanned once, it's guaranteed that the remaining elements are the majority ones.

    class Solution {
    public:
        int majorityElement(vector<int> &num) {
            int i = 0;
            int j = 1;
            while ( j < num.size() )
            {
                if ( num[i] != num[j] )
                {
                    swap(num[i+1], num[j]);
                    i += 2;
                }
                ++j;
            }
            return num[i];
        }
    };

  • 0
    G

    Basically it's the same idea as Moore voting algorithm whose classical implementation is to use an integer to record and you swap elements.


Log in to reply
 

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