Data Structures and Algorithms Series – Majority Number (Boyer–Moore majority vote algorithm)


acm-association-computing-machinery Data Structures and Algorithms Series - Majority Number (Boyer–Moore majority vote algorithm) algorithms c / c++ data structure

acm-association-computing-machinery

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it in O(n) time and O(1) space complexity.

A simple example: Given [1, 1, 1, 1, 2, 2, 2], return 1 because the number 1 has appeared 4 times which is bigger than half size i.e. 3.5 times.

The very straightforward approach will be using a hashmap to record the number of occurrences for each number, and return the majority once its counter exceeds half size.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    /*
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    int majorityNumber(vector<int> &nums) {
        unordered_map<int, int> counter;
        int half = nums.size() / 2;
        for (auto n: nums) {
            if (counter.count(n) == 0) {
                counter[n] = 0;
            } 
            counter[n] ++;
            if (counter[n] >= half) {
                return n;
            }
        }
        return -1; // not found
    }
};
class Solution {
public:
    /*
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    int majorityNumber(vector<int> &nums) {
        unordered_map<int, int> counter;
        int half = nums.size() / 2;
        for (auto n: nums) {
            if (counter.count(n) == 0) {
                counter[n] = 0;
            } 
            counter[n] ++;
            if (counter[n] >= half) {
                return n;
            }
        }
        return -1; // not found
    }
};

The unordered_map has complexity of O(1) in inserting and querying (worst case O(n)) and the above algorithm O(n) time complexity but O(n) space complexity.

Boyer–Moore majority vote algorithm

The Boyer–Moore majority vote algorithm is a O(N) one-pass algorithm that only needs O(1) constant space.

It works by only recording the counter for the current majority candidate. If there exists a majority, the algorithm guarantees to find it, otherwise it will output one of the sequence numbers as it finds it. A second pass is required to check if there is a majority. Let’s take [1 1 1 2 2 3 1] for example, m is the current majority candidate and c is the counter. When c is zero in the next round, the m is set to the current number in the iteration.

When the current number is the same as ‘candidate’, we increment the counter (vote) otherwise, we decrement the counter (de-vote).

[*1 1 1 2 2 3 1] m = 1, c = 1
[1 *1 1 2 2 3 1] m = 1, c = 2
[1 1 *1 2 2 3 1] m = 1, c = 3
[1 1 1 *2 2 3 1] m = 1, c = 2
[1 1 1 2 *2 3 1] m = 1, c = 1
[1 1 1 2 2 *3 1] m = 1, c = 0
[1 1 1 2 2 3 *1] m = 1, c = 1

The second pass we know that m=1 is the majority. The entire process is illustrated in the following C++ code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    /*
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    int majorityNumber(vector<int> &nums) {
        int c = 0, m = nums[0];
        for (int i = 0; i < nums.size(); ++ i) {
            if (c == 0) {
                m = nums[i];
                c ++;
            } else if (m == nums[i]) {
                c ++;
            } else {
                c --;   
            }
        }
        // check if there is a majority
        int counter = 0;
        for (int i : nums) {
            if (i == m) counter++;
        }
        if (counter < (nums.size() + 1) / 2) return -1;        
        return m;
    }
};
class Solution {
public:
    /*
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    int majorityNumber(vector<int> &nums) {
        int c = 0, m = nums[0];
        for (int i = 0; i < nums.size(); ++ i) {
            if (c == 0) {
                m = nums[i];
                c ++;
            } else if (m == nums[i]) {
                c ++;
            } else {
                c --;   
            }
        }
        // check if there is a majority
        int counter = 0;
        for (int i : nums) {
            if (i == m) counter++;
        }
        if (counter < (nums.size() + 1) / 2) return -1;        
        return m;
    }
};

You may also like: ACM 解题报告 – O(n)找多数算法

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
530 words
Last Post: SteemTools Update: Account Profile Lookup + Steem Blockchain Information
Next Post: JobTools Update: Adding Min Salary Criteria + Company List!

The Permanent URL is: Data Structures and Algorithms Series – Majority Number (Boyer–Moore majority vote algorithm)

Leave a Reply