博文中会简要介绍Leetcode P0229题目分析及解题思路。
“Majority Element II”是一道难度中等偏上的题目，官方给的空间复杂度为O(1)的解法这里不再阐述，本文只给出使用HashTable的最直接的思路。
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Follow-up: Could you solve the problem in linear time and in O(1) space?
这道题的思路是维护一个HashTable来计算每个不同元素出现的次数，对出现次数超过1/3的元素，我们将其加入数组并且维护当前数组内元素无重复。
以下是Java的题解代码实现。
class Solution {
public List<Integer> majorityElement(int[] nums) {
Map<Integer, Integer> num2CountMap = new HashMap<>();
List<Integer> majorities = new ArrayList<>();
Set<Integer> majoritySet = new HashSet<>();
int N = nums.length;
for (int num: nums) {
num2CountMap.put(num, num2CountMap.getOrDefault(num, 0)+1);
if (num2CountMap.get(num) > N/3 && !majoritySet.contains(num)) {
majorities.add(num);
majoritySet.add(num);
}
}
return majorities;
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
unordered_map<int, int> num2count;
vector<int> majorities;
int N = nums.size();
for (int num: nums) {
++num2count[num];
if (num2count[num] > N/3) {
if (majorities.empty()) {
majorities.push_back(num);
}
else {
if (majorities[0] != num) {
majorities.push_back(num);
return majorities;
}
}
}
}
return majorities;
}
};