leetcode

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 };