169. Majority Element#

Brute-force#

 1public int majorityElement(int[] nums) {
 2  int size = nums.length / 2;
 3
 4  for (int i = 0; i < nums.length; i++) {
 5    int occurences = 0;
 6
 7    for (int j = 0; j < nums.length; j++) {
 8      if (nums[i] == nums[j]) {
 9        occurences++;
10      }
11    }
12
13    if (occurences > size) {
14      return nums[i];
15    }
16  }
17
18  return -1;
19}

Using HashMap#

 1public int majorityElement(int[] nums) {
 2  Map<Integer, Integer> count = new HashMap<>();
 3  int n = nums.length / 2;
 4
 5  for (int num : nums) {
 6    int currentCount = count.merge(num, 1, Integer::sum);
 7    if (currentCount > n) {
 8      return num;
 9    }
10  }
11  return -1;
12}

Boyer–Moore majority vote algorithm#

 1public int majorityElement(int[] nums) {
 2  int count = 0;
 3  int result = -1;
 4
 5  for (int i = 0; i < nums.length; i++) {
 6    if (count == 0) result = nums[i];
 7
 8    if (nums[i] == result) {
 9      count++;
10    } else {
11      count--;
12    }
13  }
14
15  return result;
16}