C++ Coding Exercise – Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array.

This is another easy puzzle at https://leetcode.com/problems/majority-element/

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

We use a unordered_map to store the number of appearances. Then a second loop checks if the counter is bigger than n/2 times. However the compiler may warn you that the function may not return values in all paths.

–EOF (The Ultimate Computing & Technology Blog) —