leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0169.cpp (695B)

      1 // Naive Solution
      2 class Solution {
      3   public:
      4     int majorityElement(const vector<int> &nums) {
      5         unordered_map<int, unsigned> um;
      6         for (int n : nums)
      7             um[n]++;
      8         for (auto [k, v] : um)
      9             if (v > (nums.size() / 2)) return k;
     10         return -1;
     11     }
     12 };
     13 
     14 // Boyer-Moore Algorithm: O(n) time, O(1) space
     15 class Solution {
     16   public:
     17     int majorityElement(const vector<int> &nums) {
     18         int candid = nums[0], count = 1;
     19         for (int i = 1; i < nums.size(); i++) {
     20             if (!count) candid = nums[i];
     21             if (candid == nums[i])
     22                 count++;
     23             else
     24                 count--;
     25         }
     26         return candid;
     27     }
     28 };