229. Majority Element II

Description:

https://leetcode.com/problems/majority-element-ii/#/description

Algorithm:

Traverse the array for 2 times.

The first pass:

Use two candidate to record the most recent words.

• if nums[i] == candidate, count++
• if nums[i] != candidate, count–

The second pass:
Check the number of appearance of the candidates.

Code:

class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int candidate1 = INT_MIN, candidate2 = INT_MIN;
int count1 = 0, count2 = 0;
for (int i = 0; i < nums.size();i++)
{
if (nums[i] == candidate1)
count1++;
else if (nums[i] == candidate2)
count2++;
else if (count1 == 0)
{
candidate1 = nums[i];
count1 = 1;
}
else if (count2 == 0)
{
candidate2 = nums[i];
count2 = 1;
}
else
{
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int i = 0; i < nums.size();i++)
{
if (nums[i] == candidate1)
count1++;
else if (nums[i] == candidate2) // Here it must be else if rather than if. If the array = {INT_MIN}, candidate1 and candidate2 would both be INT_MIN. And if you use if here, the word will be counted for two times.
count2++;
}
vector <int> result;
if (count1 > nums.size() / 3)
result.push_back(candidate1);
if (count2 > nums.size() / 3)
result.push_back(candidate2);
return result;
}
};

Timing & Space:

O(n) & O(1)