Description
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.
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2
思路
解法一
纯暴力,使用一个哈希 map 记录数据出现的个数,遍历数组,当符合 majority element 的元素出现时就 return。
时间复杂度:O(n)
空间复杂度:O(n)
耗时 24 ms, Memory 9.1 MB, ranking 51%
class Solution {
public:
int majorityElement(const vector<int> &nums) {
unordered_map<int, int> m; // mapping from a number to times that it appears
int mj_element = nums[0];
for (int i = 0; i < nums.size(); ++i) {
auto iter = m.find(nums[i]);
if (iter == m.end()) {
m[nums[i]] = 1;
} else {
iter->second += 1;
if (iter->second > nums.size()/2) { // find the majority element
mj_element = iter->first;
break;
}
}
}
return mj_element;
}
};
解法二
Moore Voting 算法,使用该算法的前提是数组必须存在一个 majorityElement 且它的出现频数大于数组元素数目的一半。
时间复杂度:O(n)
空间复杂度:O(1)
耗时 16 ms, Memory 8.8 MB, ranking 95.6%
class Solution {
public:
int majorityElement(const vector<int> &nums) {
int mj_element = nums[0]; // candidate in Moore Voting algorithm
int count = 1; // counter in Moore Voting algorithm
for (int i = 1; i < nums.size(); ++i) {
if (mj_element == nums[i]) {
++count;
} else {
--count;
if (!count) {
mj_element = nums[i];
count = 1;
}
}
}
return mj_element;
}
};
参考
- 《[LeetCode] 169. Majority Element 求大多数》:https://www.cnblogs.com/grandyang/p/4233501.html