# Majority Number

## Question

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

## Analysis

The Boyer-Moore Vote Algorithm solves the majority vote problem in linear time O(n) and logarithmic space O(log n)

Moore's Page

As we sweep we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.

When we move the pointer forward over an element e:

• If the counter is 0, we set the current candidate to e and we set the counter to 1.

• If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.

When we are done, the current candidate is the majority element, if there is a majority.

## Solution

HashMap Solution

``````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 0;
}

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int listSize = nums.size();
int halfSize = listSize / 2;
int result = 0;

for (int i = 0; i < listSize; i++) {
int num = nums.get(i);

if (!map.containsKey(num)) {
map.put(num, 1);
} else {
map.put(num, 1 + map.get(num));
}

if (map.get(num) > halfSize) {
result = num;
}
}

return result;
}
}``````

Boyer–Moore majority vote algorithm

``````public class Solution {
/**
* @param nums: a array of integers
* @return: find a majority element
*/
public int majorityElement(int[] nums) {
int n = nums.length;
int candidate = nums[0], counter = 0;
for (int i : nums) {
if (counter == 0) {
candidate = i;
counter = 1;
} else if (candidate == i) {
counter++;
} else {
counter--;
}
}

counter = 0;
for (int i : nums) {
if (i == candidate) counter++;
}
if (counter < (n + 1) / 2) return -1;
return candidate;
}
}``````

Last updated