Moore voting algorithm


  • 13
    S
    // Moore voting algorithm: Runtime: O(n), Space O(1)
    // We maintain a current candidate and a counter initialized to 0. 
    // As we iterate the array, we look at the current element x: 
    // If the counter is 0, we set the current candidate to x and the counter to 1.
    // If the counter is not 0, we increment or decrement the counter based on whether x is the current candidate. 
    int majorityElement(vector<int> &num) {
        int cur = 0;
        int cnt = 0;
        for (int x : num) {
            if (cnt == 0) cur = x, cnt = 1;
            else if (cur == x) ++cnt;
            else --cnt;
        }
        return cur;
    }

Log in to reply
 

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