# Majority Number

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.

Example

Given [1, 1, 1, 1, 2, 2, 2], return 1

Challenge

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

This problem could be solved using Boyer–Moore majority vote algorithm.

```
public class Solution {
/**
* @param nums: a list of integers
* @return: find a majority number
*/
public int majorityNumber(ArrayList<Integer> nums) {
if (nums == null || nums.size() == 0) {
return -1;
}
int candidate = 0, counter = 0;
for (int i : nums) {
if (counter == 0) {
candidate = i;
counter = 1;
} else if (i == candidate) {
counter++;
} else if (i != candidate) {
counter--;
}
}
return candidate;
}
}
```

Hope this helps,

Michael