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.
Solution1:Moore voting
思路:主要思想是每次找到两个不同的元素 一起弃掉,最终剩下的就是the majority element hat appears more than ⌊ n/2 ⌋ times.
Time Complexity: O(N) Space Complexity: O(1)
Solution1b:Rount1: Moore voting
Time Complexity: O(N) Space Complexity: O(1)
Solution2:Sorting后返回 nums中间元素
思路:主要思想是每次找到两个不同的元素 一起弃掉,最终剩下的就是the majority element hat appears more than ⌊ n/2 ⌋ times.
Time Complexity: O(NlogN) Space Complexity: O(1)
Solution3:Hashmap count
Time Complexity: O(N) Space Complexity: O(N)
Solution4:Divide and Conquer 分治
思路:类似归并排序思想,Divide成左右两部分,分别得到左右部分的Majority Element lm, rm 。Conquer: 在当前序列上分别count lm和rm,作为本level的Majority Element 回传。
Time Complexity: O(NlogN) Space Complexity: O(logN)递归缓存
Solution5:Bit manipulation
思路:32位int,分别统计各位最多次的0or1,因为是> n/2 次,所以一定是结果一定都是majority element的各位,再回组 成结果
Time Complexity: O(N) Space Complexity: O(1)
Solution6:randomly pick
思路:随机选一个 遍历看他是不是Majority element
Time Complexity: O(N^2 with low概率) Space Complexity: O(1)
Solution1 Code:
class Solution {
// Moore voting algorithm
public int majorityElement(int[] nums) {
int candidate = 0;
int count = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] == candidate) count++;
else if(count == 0) {
candidate = nums[i];
count = 1;
}
else {
count--;
}
}
return candidate;
}
}
Solution1b Code:
class Solution {
public int majorityElement(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int candidate = 0;
int count = 0;
for(int i = 0; i < nums.length; i++) {
if(count == 0) {
candidate = nums[i];
count = 1;
}
else if(nums[i] == candidate) {
count++;
}
else {
count--;
}
}
return candidate;
}
}
Solution2 Code:
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
Solution3 Code:
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int ret = 0;
for (int num: nums) {
if (!map.containsKey(num))
map.put(num, 1);
else {
map.put(num, map.get(num) + 1);
}
if(map.get(num) > nums.length / 2) {
ret = num;
break;
}
}
return ret;
}
}
Solution4 Code:
class Solution {
public int majorityElement(int[] nums) {
return majority(nums, 0, nums.length - 1);
}
private int majority(int[] nums, int left, int right) {
if(left == right) return nums[left];
int mid = left + (right - left) / 2;
int lm = majority(nums, left, mid);
int rm = majority(nums, mid + 1, right);
int majority_num;
if(count_value(nums, left, right + 1, lm) > count_value(nums, left, right + 1, rm)) {
majority_num = lm;
}
else {
majority_num = rm;
}
return majority_num;
}
private int count_value(int[] nums, int start, int end, int value) {
int count = 0;
for (int i = start; i < end; i++) {
if (nums[i] == value) count ++;
}
return count;
}
}
Solution5 Code:
class Solution {
// Bit manipulation
public int majorityElement(int[] nums) {
int[] bit = new int[32];
for (int num: nums) {
for (int i = 0; i < 32; i++) {
if ((num >> (31 - i) & 1) == 1) {
bit[i]++;
}
}
}
int ret = 0;
for (int i = 0; i < 32; i++) {
bit[i] = bit[i] > nums.length / 2 ? 1 : 0;
ret += bit[i] * (1 << (31 - i));
}
return ret;
}
}