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.
Example 1:
Input: [3,2,3] Output: 3
Example 2:
Input: [2,2,1,1,1,2,2] Output: 2
M1: sort, time: O(nlogn), space: O(logn)
class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length / 2]; } }
M2: bit manipulation, time: O(n), space: O(1)
class Solution { public int majorityElement(int[] nums) { int res = 0; for(int i = 0; i < 32; i++) { int ones = 0, zeros = 0; for(int n : nums) { if(ones > nums.length / 2 || zeros > nums.length / 2) { break; } if((n & (1 << i)) != 0) { ones++; } else { zeros++; } } if(ones > zeros) { res |= (1 << i); } } return res; } }
M3: Boyer-Moore Voting Algorithm, time: O(n), space: O(1)
class Solution { public int majorityElement(int[] nums) { Integer candidate = null; int cnt = 0; for(int n : nums) { if(cnt == 0) { candidate = n; } cnt += (candidate == n) ? 1 : -1; } return candidate; } }
M4: hash table, time: O(n), space: O(n)
class Solution { public int majorityElement(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for(int n : nums) { map.put(n, map.getOrDefault(n, 0) + 1); } int res = 0; for(Map.Entry<Integer, Integer> entry : map.entrySet()) { if(entry.getValue() > nums.length / 2) { res = entry.getKey(); break; } } return res; } }
原文：https://www.cnblogs.com/fatttcat/p/13712869.html