Majority element

MajorityElement

// https://oj.leetcode.com/problems/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.

class Solution {
public:
    // Hash table
    int majorityElement_hashtable(vector<int> &num) {
        std::map <int, int> table;
        for (int n : num) {
            auto it = table.find(n);
            table[n] = it == table.end() ? 1 : (it->second + 1);
        }
        int threshold = static_cast<int>(num.size() / 2);
        int res = -1;
        for (auto const & kv : table) {
          if (kv.second > threshold) {
              threshold = kv.second;
              res = kv.first;
          }
        }
        return res;
    }
    
    // Voting algorithm
    // http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
    int majorityElement_voting(vector<int> &num) {
        int counter = 0;
        int candidate = -1;
    
        for (int n : num) {
            if (counter == 0) {
                candidate = n;
                ++counter;
            } else {
                if (candidate == n) {
                    ++counter;
                } else {
                    --counter;
                }
            }
        }
        return candidate;
    }
};