229 Majority Element II
Given an integer array of size n, find all elements that appear more than
⌊ n/3 ⌋times. The algorithm should run in linear time and in O(1) space.vector<int> majorityElement(vector<int> &elements)
{
int n_over_3 = elements.size() / 3;
unordered_map<int,int> int_freq;
for (int i = 0; i < elements.size(); i++) {
if (int_freq.find(elements.at(i)) != int_freq.end()) {
int_freq[elements.at(i)]++;
}
else {
int_freq.insert(make_pair(elements.at(i), 1));
}
}
vector<int> majority_elements;
for (auto i : int_freq) {
if (i.second > n_over_3) {
majority_elements.push_back(i.first);
}
}
return majority_elements;
}
Last modified 3yr ago