# Majority Number II

## Question

Given an array of integers,
the majority number is the number that occurs more than 1/3 of the size of the array.

Find it.

Example
Given [1, 2, 1, 2, 1, 3, 3], return 1.

Note
There is only one majority number in the array.

Challenge
O(n) time and O(1) extra space.


## 题解

Majority Number 的升级版，之前那道题是『两两抵消』，这道题自然则需要『三三抵消』，不过『三三抵消』需要注意不少细节，比如两个不同数的添加顺序和添加条件。

### C++

class Solution {
public:
/**
* @param nums: A list of integers
* @return: The majority number occurs more than 1/3.
*/
int majorityNumber(vector<int> nums) {
if (nums.empty()) return -1;

int k1 = 0, k2 = 0, c1 = 0, c2 = 0;
for (auto n : nums) {
if (!c1 || k1 == n) {
k1 = n;
c1++;
} else if (!c2 || k2 == n) {
k2 = n;
c2++;
} else {
c1--;
c2--;
}
}

c1 = 0;
c2 = 0;
for (auto n : nums) {
if (n == k1) c1++;
if (n == k2) c2++;
}
return c1 > c2 ? k1 : k2;
}
};


### Java

public class Solution {
/**
* @param nums: A list of integers
* @return: The majority number that occurs more than 1/3
*/
public int majorityNumber(ArrayList<Integer> nums) {
if (nums == null || nums.isEmpty()) return -1;

// pair
int key1 = -1, key2 = -1;
int count1 = 0, count2 = 0;
for (int num : nums) {
if (count1 == 0) {
key1 = num;
count1 = 1;
continue;
} else if (count2 == 0 && key1 != num) {
key2 = num;
count2 = 1;
continue;
}
if (key1 == num) {
count1++;
} else if (key2 == num) {
count2++;
} else {
count1--;
count2--;
}
}

count1 = 0;
count2 = 0;
for (int num : nums) {
if (key1 == num) {
count1++;
} else if (key2 == num) {
count2++;
}
}
return count1 > count2 ? key1 : key2;
}
}