# Majority Problem Set Summary C++

• Problem Majority 1 ------ Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

``````class Solution {
public:
int majorityElement(vector<int> &num) {
int majorityIndex = 0;
for (int count = 1, i = 1; i < num.size(); i++) {
num[majorityIndex] == num[i] ? count++ : count--;
if (count == 0) {
majorityIndex = i;
count = 1;
}
}
return num[majorityIndex];
}
};

``````

Problem Majority 2 ------ 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.

``````class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n=nums.size();
vector<int> result;

int count1=0, count2=0;
int result1=INT_MAX, result2=INT_MAX;

for(int num:nums){
if(num==result1) count1++;
else if(num==result2) count2++;
else if(count1==0) { result1=num; count1=1; }
else if(count2==0) { result2=num; count2=1; }
else { count1--; count2--; }
}

count1=count2=0;
for(int num:nums){
if(num==result1) count1++;
else if(num==result2)  count2++;
}

cout<<result1<<":"<<count1<<endl;
cout<<result2<<":"<<count2<<endl;

if(count1>n/3) result.push_back(result1);
if(count2>n/3) result.push_back(result2);

return result;
}
};
``````

Problem Majority 3 ------ Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array.

``````class Solution {
public:
/**
* @param nums: A list of integers
* @param k: As described
* @return: The majority number
*/
int majorityNumber(vector<int> nums, int k) {
const int n = nums.size();
unordered_map<int, int> hash;

for (const auto& i : nums) {
++hash[i];
// Detecting k items in hash, at least one of them must have exactly
// one in it. We will discard those k items by one for each.
// This action keeps the same mojority numbers in the remaining numbers.
// Because if x / n  > 1 / k is true, then (x - 1) / (n - k) > 1 / k is also true.
if (hash.size() == k) {
auto it = hash.begin();
while (it != hash.end()) {
if (--(it->second) == 0) {
hash.erase(it++);
} else {
++it;
}
}
}
}

/** just re-count the possible candidate number **/
// Resets hash for the following counting.
for (auto& it : hash) {
it.second = 0;
}

// Counts the occurrence of each candidate integer.
for (const auto& i : nums) {
auto it = hash.find(i);
if (it != hash.end()) {
++it->second;
}
}

// Selects the integer which occurs > n / k times.
vector<int> ret;
for (const pair<int, int>& it : hash) {
if (it.second > static_cast<double>(n) / k) {
ret.emplace_back(it.first);
}
}

return ret[0];
}
};

``````

• ``````
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n=nums.size();
vector<int> result;

int count1=0, count2=0;
int result1=INT_MAX, result2=INT_MAX;

for(int num:nums){
if(num==result1) { count1++; continue; }
if(num==result2) { count2++; continue; }
if(count1==0) { result1=num; count1=1; continue; }
if(count2==0) { result2=num; count2=1; continue; }
count1--; count2--;
}

count1=count2=0;
for(int num:nums){
if(num==result1) count1++;
else if(num==result2)  count2++;
}

if(count1>n/3) result.push_back(result1);
if(count2>n/3) result.push_back(result2);

return result;
}
};
``````

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