C++ solution using Moore's voting algorithm - O(n) runtime comlexity an no extra array or hash table


  • 69
    S

    This can be solved by Moore's voting algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element. Below code loops through each element and maintains a count of the element that has the potential of being the majority element. If next element is same then increments the count, otherwise decrements the count. If the count reaches 0 then update the potential index to the current element and sets count to 1.

    int majorityElement(vector<int> &num) {
        int majorityIndex = 0;
        for (int count = 1, i = 1; i < num.size(); i++) {
            num[majorityIndex] == num[i] ? count++ : count--;
            if (count == 0) {
                majorityIndex = i;
                count = 1;
            }
        }
            
        return num[majorityIndex];
    }

  • 0
    S

    Your answer is perfect. However, I want to learn more about the Moore's voting algorithm you mentioned. Can you share any website of the algorithm to me? Thanks a lot.


  • 0

    Here is a step by step illustrative example from the original author.


  • 0
    S

    Thanks for your reply. :)


  • 0
    S

    BTW, the efficiency can be improved further by updating the loop condition as follows: "for (int count = 1, i = 1; i < num.size() && count <= num.size(); i++) {". This will allow a possible early exit as soon as we figure out that the count of an occurrence is more than half of the total number of elements in the array.


  • 0
    B

    great but it requires some knowledge of voting algorithm beforehand....


  • 0
    S

    bboczeng, you are right it needs the prior knowledge of the voting algorithm. At the same time anyone who is asking this question is not really looking for a brute force method answer. :) I think the idea of this forum is to share such ideas and algorithms so the members are more aware and smatter? :)


  • 0
    X

    Here is a very helpful blog I found clearly explaining how the Moore's voting algorithm works. It also shows a way to run it in parallel.

    http://gregable.com/2013/10/majority-vote-algorithm-find-majority.html


  • 0
    D

    This is very helpful! The parallel part is amazing


  • 0
    A

    thx a lot! It is really save space and time!


  • 1
    D

    A python version. Thanks a lot for sharing the idea.

    class Solution:
        # @param num, a list of integers
        # @return an integer
        def majorityElement(self, num):
            
            if not num:
                return None
            
            selectedElement = num[0]
            count = 0
            total = len(num)
            
            for n in num:
                if count > total/2:
                    return selectedElement
                
                if n == selectedElement:
                    count +=1
                elif count == 1:
                    selectedElement = n
                else:
                    count -= 1
                        
            return selectedElement
    

  • 0
    I

    shouldn't it be "count <= num.size() / 2" if intend to improve?


  • 0
    D
    This post is deleted!

  • 2

    Not sure if it works with this input : 1,1,3,3,3,9,1,9,9,3, the answer I get with the above algo is 9 whereas it should be 3.


  • 0
    S

    Please read the question carefully, your input {1,1,3,3,3,9,1,9,9,3} is invalid. The question said "The majority element is the element that appears more than ⌊ n/2 ⌋ times." However, your input only contains four 3, while the size of the set is 10. 4 < 10/2. So it has a "wrong" answer. In fact, in this case, it has no correct answer.


  • 0

    Its actually the following assumption in the question : You may assume that the array is non-empty and the majority element always exist in the array actually which makes the input wrong, bcoz otherwise, we would need to make sure that the element num[majorityIndex] would be > n/2 .


Log in to reply
 

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