6 Suggested Solutions in C++ with Explanations


  • 316

    Well, if you have got this problem accepted, you may have noticed that there are 7 suggested solutions for this problem. The following passage will implement 6 of them except the O(n^2) brute force algorithm.


    Hash Table

    The hash-table solution is very straightforward. We maintain a mapping from each element to its number of appearances. While constructing the mapping, we update the majority element based on the max number of appearances we have seen. Notice that we do not need to construct the full mapping when we see that an element has appeared more than n / 2 times.

    The code is as follows, which should be self-explanatory.

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            unordered_map<int, int> counts; 
            int n = nums.size();
            for (int i = 0; i < n; i++)
                if (++counts[nums[i]] > n / 2)
                    return nums[i];
        }
    };
    

    Sorting

    Since the majority element appears more than n / 2 times, the n / 2-th element in the sorted nums must be the majority element. This can be proved intuitively. Note that the majority element will take more than n / 2 positions in the sorted nums (cover more than half of nums). If the first of it appears in the 0-th position, it will also appear in the n / 2-th position to cover more than half of nums. It is similar if the last of it appears in the n - 1-th position. These two cases are that the contiguous chunk of the majority element is to the leftmost and the rightmost in nums. For other cases (imagine the chunk moves between the left and the right end), it must also appear in the n / 2-th position.

    The code is as follows, being very short if we use the system nth_element (thanks for @qeatzy for pointing out such a nice function).

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
            return nums[nums.size() / 2];
        } 
    };
    

    Randomization

    This is a really nice idea and works pretty well (16ms running time on the OJ, almost fastest among the C++ solutions). The proof is already given in the suggested solutions.

    The code is as follows, randomly pick an element and see if it is the majority one.

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int n = nums.size();
            srand(unsigned(time(NULL)));
            while (true) {
                int idx = rand() % n;
                int candidate = nums[idx];
                int counts = 0; 
                for (int i = 0; i < n; i++)
                    if (nums[i] == candidate)
                        counts++; 
                if (counts > n / 2) return candidate;
            }
        }
    };
    

    Divide and Conquer

    This idea is very algorithmic. However, the implementation of it requires some careful thought about the base cases of the recursion. The base case is that when the array has only one element, then it is the majority one. This solution takes 24ms.

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            return majority(nums, 0, nums.size() - 1);
        }
    private:
        int majority(vector<int>& nums, int left, int right) {
            if (left == right) return nums[left];
            int mid = left + ((right - left) >> 1);
            int lm = majority(nums, left, mid);
            int rm = majority(nums, mid + 1, right);
            if (lm == rm) return lm;
            return count(nums.begin() + left, nums.begin() + right + 1, lm) > count(nums.begin() + left, nums.begin() + right + 1, rm) ? lm : rm;
        }
    }; 
    

    Moore Voting Algorithm

    A brilliant and easy-to-implement algorithm! It also runs very fast, about 20ms.

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int major, counts = 0, n = nums.size();
            for (int i = 0; i < n; i++) {
                if (!counts) {
                    major = nums[i];
                    counts = 1;
                }
                else counts += (nums[i] == major) ? 1 : -1;
            }
            return major;
        }
    };
    

    Bit Manipulation

    Another nice idea! The key lies in how to count the number of 1's on a specific bit. Specifically, you need a mask with a 1 on the i-the bit and 0 otherwise to get the i-th bit of each element in nums. The code is as follows.

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int major = 0, n = nums.size();
            for (int i = 0, mask = 1; i < 32; i++, mask <<= 1) {
                int bitCounts = 0;
                for (int j = 0; j < n; j++) {
                    if (nums[j] & mask) bitCounts++;
                    if (bitCounts > n / 2) {
                        major |= mask;
                        break;
                    }
                }
            } 
            return major;
        } 
    };

  • 1
    H

    for the hash table method,just change the code after counts[nums[i]]++ to if(counts[nums[i]] > n/2) { major = nums[i]; break; }.
    it is more simple.


  • 0

    Hi, huzhp. I have further shortened the code. Thank you for your nice remind.


  • 7
    Q

    I think for the sorting approach, std::nth_element should be used instead of std::sort, since no need to do a full sort.


  • 0

    Hi, qeatzy. Great thanks for pointing out the nth_element function. I have not known it before :-) BTW, I have updated my code.


  • 7
    V

    I think the Divide and Conquer code have some problem. The runtime complexity of Divide and Conquer should be T(n) = T(n/2) + 2n = O(n log n), but the worst case of your code is O(n^2).

    This is my Divide and Conquer code:

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            return majority(nums, 0, nums.size() - 1);
        }
    private:
        int majority(vector<int>& nums, int left, int right) {
            if (left == right) return nums[left];
            int mid = left + ((right - left) >> 1);
            int lm = majority(nums, left, mid);
            int rm = majority(nums, mid + 1, right);
            if (lm == rm) return lm;
            return count(nums.begin() + left, nums.begin() + right + 1, lm) > count(nums.begin() + left, nums.begin() + right + 1, rm) ? lm : rm;
        }
    };

  • 0

    Hi, vikotse. Thank you for pointing out the redundant counting and the nice function count. I have updated my code and it becomes much faster now :-)


  • -5
    E

    I think there is something wrong with the Moore Voting Algorithm. Your code won't pass cases like [1, 1,-1, -1, 2, 1 ]. Your code will return 2. The problem is that you need to judge whether the cnt is 0 in the end of each loop instead of at the beginning.

    Here is my code using your idea:

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int maj = nums[0], cnt = 1;
            for (int i = 1; i < nums.size(); ++i) {
                cnt += (maj == nums[i]) ? 1 : -1;
                if (cnt == 0) {
                    maj = nums[i];
                    cnt = 1;
                }
            }
            return maj;
        }
    };

  • 0

    Hi, EdwardDing. Well, your test case [1, 1, -1, -1, 2, 1] does not have a majority element which satisfies the requirements of the problem statement:

    The majority element is the element that appears more than ⌊ n/2 ⌋ times.

    However, in your test case, no more appears more than n / 2 = 3 times.


  • 0
    Z

    @jianchao.li.fighter Does sort really work? How about the array contains string, int, or even an array?


  • 0

    Hi, do you mean that the array has mixed types of elements? Well, I believe such cases may appear in real world. However, just for the sake of the algorithm of this problem, considering such cases seems unnecessary...


  • 0
    O

    so completeeeee nice sharing think you!


  • 0
    Z

    Gotcha, thank you @jianchao.li.fighter


  • 0
    T

    Thanks a lot. Learnt 10 things from this post. :)


  • 0

    @tareque_md It is great that you find it useful :-)


  • 0
    S

    Thanks a lot! So nice


  • 0
    C

    @jianchao.li.fighter Would you mind explaining me your Divide and conquer approach.It looks so fancy to me.Thanks :)


  • 1
    K

    Amazing summary!
    For Divide and Conquer solution, it's O(nlgn) algorithm. It can achieve such good performance is because if (lm == rm) return lm; It saves a lot overhead from count functions especially in this case. Very brilliant.

    The only surprise solution is Randomization. I suppose performance of this solution would be random as well. It's best case is O(n) and the worst case is O(n^2). How can it beat Moore Voting Algorithm?


  • 0
    A

    @kenan3 I agree that randomization is O(n) best, O((n^2)/2) worst. It can't beat Boyer-Moore.
    You can't judge the algorithm by a single run since the run time on leetcode can vary significantly depending on the load of the machine at your submit time,


  • 0
    X

    Thank you for sharing!


Log in to reply
 

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