leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0169.cpp (695B)

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