Leetcode: Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Leetcode的官方答案给的解答很好，我的方法是HashMap. 除了brute force和sorting常见方法以外，还有几个方法，思路都还不错，1是我的方法，我觉得2、4、5都是不错的思路。

1. Runtime: O(n), Space: O(n) — Hash table: Maintain a hash table of the counts of each element, then find the most common one.
2. Average runtime: O(n), Worst case runtime: Infinity — Randomization: Randomly pick an element and check if it is the majority element. If it is not, do the random pick again until you find the majority element. As the probability to pick the majority element is greater than 1/2, the expected number of attempts is < 2.
3. Runtime: O(n log n) — Divide and conquer: Divide the array into two halves, then find the majority element A in the first half and the majority element B in the second half. The global majority element must either be A or B. If A == B, then it automatically becomes the global majority element. If not, then both A and B are the candidates for the majority element, and it is suffice to check the count of occurrences for at most two candidates. The runtime complexity, T(n) = T(n/2) + 2n = O(n logn).
4. Runtime: O(n), Space: O(1) — Moore voting algorithm: We maintain a current candidate and a counter initialized to 0. As we iterate the array, we look at the current element x:
   
   1. If the counter is 0, we set the current candidate to x and the counter to 1.
   2. 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).
5. Runtime: O(n) — 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.

 1 public class Solution {
 2     public int majorityElement(int[] num) {
 3         int n = num.length;
 4         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
 5         for (int elem : num) {
 6             if (map.containsKey(elem)) {
 7                 map.put(elem, map.get(elem)+1);
 8             }
 9             else {
10                 map.put(elem, 1);
11             }
12         }
13         for (int item : map.keySet()) {
14             if (map.get(item) > n/2) {
15                 return item;
16             }
17         }
18         return -1;
19     }
20 }

位操作法

复杂度

时间 O(N) 空间 O(1)

思路

假设一个数是最多只有32位的二进制数，那么我们从第一位到第32位，对每一位都计算所有数字在这一位上1的个数，如果这一位1的个数大于一半，说明众数的这一位是1，如果小于一半，说明大多数的这一位是0。

Best Approach: Moore voting algorithm O(N) time O(1) space

 1 class Solution {
 2     public int majorityElement(int[] nums) {
 3         int cnt = 0;
 4         int vote = -1;
 5         
 6         for (int num : nums) {
 7             if (cnt == 0) {
 8                 vote = num;
 9             }
10             if (vote == num) cnt ++;
11             else cnt --;
12         }
13         return vote;
14     }
15 }