Array Divide and Conquer Bit Manipulation
Description:
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.
我的第一种解法特别蠢，想着个数超过n/2，肯定有连续的，找出连续的就行了，当然其他元素也可以连续....真的怀疑自己脑子少根筋...
好一点的解法要引入count，至于这个变量记录什么是很讲究的，为了使时间复杂度尽量降，就用一个count记录整个数组的遍历过程。count初始化为0，当当前遍历的数字与初定的major相同，count++，否则count--。major的值随count变为0后转成下一个数。其实这就是最大投票算法。
my Solution:
public class Solution {
public int majorityElement(int[] nums) {
int major = nums[0];
int count = 0;
for (int num : nums) {
if (count == 0) {
major = num;
count++;
} else if (major == num) {
count++;
} else {
count--;
}
}
return major;
}
}
在Discuss里看到有大牛一题多解了，此处膜拜一下
// Sorting
public int majorityElement1(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
// Hashtable
public int majorityElement2(int[] nums) {
Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();
//Hashtable<Integer, Integer> myMap = new Hashtable<Integer, Integer>();
int ret=0;
for (int num: nums) {
if (!myMap.containsKey(num))
myMap.put(num, 1);
else
myMap.put(num, myMap.get(num)+1);
if (myMap.get(num)>nums.length/2) {
ret = num;
break;
}
}
return ret;
}
// Moore voting algorithm 就是题主的解法
public int majorityElement3(int[] nums) {
int count=0, ret = 0;
for (int num: nums) {
if (count==0)
ret = num;
if (num!=ret)
count--;
else
count++;
}
return ret;
}
// 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;
}