# C++ solution for elements appear more than floor(n/k) times

• ``````  vector<int> majorityElement(vector<int>& nums) {
return majorityElement(nums, 3);
}
vector<int> majorityElement(vector<int>& nums, const int k) {
const int size_n = nums.size();
vector<int> result;
unordered_map<int, int> cand;
for (int i = 0; i < size_n; i++) {
cand[nums[i]]++;
if (cand.size() == k) {
for (auto it = cand.begin(); it != cand.end(); ) {
if (--(it->second) == 0) it = cand.erase(it);
else it++;
}
}
}
for (auto& item : cand) item.second = 0;
for (auto& item : nums) {
if (cand.count(item) > 0) cand[item]++;
}
for (auto& item : cand) {
if (item.second > size_n / k) result.emplace_back(item.first);
}
return result;
}``````

• Please check the requirements carefully. O(1) space!

• I think it is O(1) space when K is 3 since 3 is a constant.

• Hi, lchen77, I think it's because of the unordered_map<int, int> cand;

• I understand your meaning. If k == 3, then unordered_map<int, int> cand will be less than 3 too. So the space is a constant space, meaning O(1).

• My mistake. You solution is correct and a nice one!

• The code is elegant and have good scalability.

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.