Solution 1
Naive way
First, sort the array using Arrays.sort in Java. Than, scan once to find the majority element. Time complexity O(nlog(n))
public class Solution {
public int majorityElement(int[] nums) {
int length = nums.length;
if (length == 1)
return nums[0];
Arrays.sort(nums);
int prev = nums[0];
int count = 1;
for (int i = 1; i < length; i++) {
if (nums[i] == prev) {
count++;
if (count > length / 2) return nums[i];
} else {
prev = nums[i];
count = 1;
}
}
return 0;
}
}
Solution 2
Since the majority always take more than a half space, the middle element is guaranteed to be the majority.
public class Solution {
public int majorityElement(int[] nums) {
int length = nums.length;
if (length == 1)
return nums[0];
Arrays.sort(nums);
return nums[length / 2];
}
}
Solution 3 Moore voting algorithm
As we iterate the array, we look at the current element x:
- If the counter is 0, we set the current candidate to x and the counter to 1.
- If the counter is not 0, we increment or decrement the counter based on whether x is the current candidate.
After one pass, the current candidate is the majority element. Runtime complexity = O(n).
public class Solution {
public int majorityElement(int[] nums) {
int length = nums.length;
if (length == 1)
return nums[0];
int maj = nums[0];
int count = 0;
for (int i = 0; i < length; i++) {
if (count == 0) {
maj = nums[i];
count = 1;
} else if (nums[i] == maj) {
count++;
} else {
count--;
}
}
return maj;
}
}
Solution 4 Bit Manipulation
We would need 32 iterations, each calculating the number of 1's for the ith bit of all n numbers. Since a majority must exist, therefore, either count of 1's > count of 0's or vice versa (but can never be equal). The majority number’s ith bit must be the one bit that has the greater count.
Time complexity: 32 * n = T(n)
public class Solution {
public int majorityElement(int[] nums) {
int length = nums.length;
if (length == 1)
return nums[0];
int[] dig = new int[32];
for (int i = 0; i < length; i++) {
int tmp = nums[i];
for (int j = 0; j < 32; j++) {
dig[j] += tmp & 1;
tmp = tmp >> 1;
}
}
int max = 0;
int tmp = 1;
for (int i = 0; i < 32; i++) {
if (dig[i] > length / 2) {
max = max | tmp;
}
tmp = tmp << 1;
}
return max;
}
}