机考刷题之 6 LeetCode 169 多数元素

题目

分析

思路一

第一时间想到的是拿一个unordered_map/map来存储每个值对应的频率，然后遍历这个unordered_map/map再得出主要元素。

代码

class Solution { public: int majorityElement(vector<int>& nums) { unordered_map<int,int>myMap; for(auto i:nums){ myMap[i]++; } int maxCount = 0; int result = 0; for (auto& pair : myMap) { if (pair.second > maxCount) { maxCount = pair.second; result = pair.first; } } return result; } };

结果

思路二

看到了提示尝试O(n)时间复杂度和O(1)的空间复杂度，查了一下，使用到了Boyer-Moore投票法，关于这个算法的讲解，这篇文章讲得很全面，核心思想就是针对于存在主要元素的数组，将两个不同的元素两两消去，剩下的就一定是主要元素（因为确保了存在主要元素）。

代码

class Solution { public: int majorityElement(vector<int>& nums) { int candidate = 0, count = 0; for (int num : nums) { if (count == 0) { candidate = num; } count += (num == candidate) ? 1 : -1; } return candidate; } };

结果