Egbert Lin's Blog

“Life is not a race, but a journey to be savoured each step of the way” by Brian Dyson

[LeetCode] Majority Element - Solution/C++

Posted on Edited on In Disqus:

169. Majority Element

Question:

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Follow-up: Could you solve the problem in linear time and in Ｏ(1) space?

Example:

Input: nums = [3,2,3]
Output: 3

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:
  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

    • Source code

    Idea:
    The strategy is similar wtih Linked List Cycle's version 1. Use unordered_map container to store a count of element. Notice: the majority element appears more than ⌊n / 2⌋ times and therefore you should add if statment for checking.

    Time complexity: O(n)
    Space complexity: O(n)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            unordered_map<int, int> count;
            const int n = nums.size();
            for(int i = 0; i < n; i++){
                count[nums[i]]++;
                if (count[nums[i]] > n/2) return nums[i];
            }
            return -1;
        }
    };

    Version 2

    Idea:
    It is a vary specail approach. It supposes the first element as the majority, and declare a counter.

    Use a loop to go through every element, if current element is equal to the majority, count will plus 1, otherwise, count will minus 1.
    If count is equal to 0, the majority will be updated to current element, and count is set 1.

    Time complexity: O(n)
    Space complexity: O(1)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int majority = nums.front();
            int count = 0;
            
            for(int i = 0; i < nums.size(); i++){
                if(majority == nums[i]){
                    count++;
                }else if(--count == 0){
                    majority = nums[i];
                    count = 1;
                }
            }
            return majority;
        }
    };

    Version 3

    Idea:
    You have more than fifty opporunity to get the answer, because the majority element appears more than n / 2 times.
    Therefore, the strategy is a random approach that a random value is exist in array, then it compares with all element, if it appears more than n /2 times, it is the answer.

    Note:
    The formular of random is:
    rand%(max - min + 1) + min
    E.g., you want to get a random number between 5 and 10

    • min ← 5
    • max ← 10
    • randValue ← rand()%(10 - 5 + 1) + 5

    // if you don't plus 1 like this: rand()%(10 - 5), you will attain a random value between 0 to 4. So it must plus 1!

    Time complexity: O(n)
    Space complexity: O(1)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            srand(time(nullptr));
            int n = nums.size();
            
            while(true){
                int majority = nums[rand()%n];
                int count = 0;
                for(int i = 0; i < n; i++){
                    if(majority == nums[i]) count++;
                    if(count > n/2) return majority;
                }
            }
            return -1;
        }
    };