Majority Element 解答

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))

 1 public class Solution {
 2     public int majorityElement(int[] nums) {
 3         int length = nums.length;
 4         if (length == 1)
 5             return nums[0];
 6         Arrays.sort(nums);
 7         int prev = nums[0];
 8         int count = 1;
 9         for (int i = 1; i < length; i++) {
10             if (nums[i] == prev) {
11                 count++;
12                 if (count > length / 2) return nums[i];
13             } else {
14                 prev = nums[i];
15                 count = 1;
16             }
17         }
18         return 0;
19     }
20 }

Solution 2

Since the majority always take more than a half space, the middle element is guaranteed to be the majority.

1 public class Solution {
2     public int majorityElement(int[] nums) {
3         int length = nums.length;
4         if (length == 1)
5             return nums[0];
6         Arrays.sort(nums);
7         return nums[length / 2];
8     }
9 }

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).

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

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)

 1 public class Solution {
 2     public int majorityElement(int[] nums) {
 3         int length = nums.length;
 4         if (length == 1)
 5             return nums[0];
 6         int[] dig = new int[32];
 7         for (int i = 0; i < length; i++) {
 8             int tmp = nums[i];
 9             for (int j = 0; j < 32; j++) {
10                 dig[j] += tmp & 1;
11                 tmp = tmp >> 1;
12             }
13         }
14         int max = 0;
15         int tmp = 1;
16         for (int i = 0; i < 32; i++) {
17             if (dig[i] > length / 2) {
18                 max = max | tmp;
19             }
20             tmp = tmp << 1;
21         }
22         return max;
23     }
24 }