Q:
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.
A：
使用Hashmap最基本的思路。
public int majorityElement(int[] nums) {
Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();
//Hashtable<Integer, Integer> myMap = new Hashtable<Integer, Integer>();
int target = 0;
for (int num: nums) {
if (!myMap.containsKey(num)) //如果出現(xiàn)一個(gè)數(shù)之前不在map里
myMap.put(num, 1); //放進(jìn)去 <原值，計(jì)數(shù)>
else
myMap.put(num, myMap.get(num)+1); //如果存在，計(jì)數(shù)+1
if (myMap.get(num)>nums.length/2) {
target = num;
break; //不一定traverse整個(gè)nums，也許結(jié)果就出來(lái)了
}
}
return target;
}
Boyer–Moore majority vote algorithm
基本思路：最初設(shè)置兩個(gè)值，一個(gè)target，一個(gè)count，分別進(jìn)行統(tǒng)計(jì)。target從選取nums[0]開始，每當(dāng)計(jì)數(shù)變成0的時(shí)候，target值就會(huì)換。其實(shí)可以按“消除”的想法去理解，比如target值是3，連續(xù)出現(xiàn)了四次，那么這個(gè)時(shí)候count=4，但是連續(xù)又連續(xù)出現(xiàn)了五次不是3的值，那么count不僅被清0了，而且target的值也被替換了，從新開始統(tǒng)計(jì)。到最后，都“消除”完了，還能成為target，說(shuō)明具有數(shù)量上的優(yōu)勢(shì)，也就是我們要找的“大量”、“總數(shù)過(guò)半”的值。
public int majorityElement(int[] num) {
int target = num[0], count = 1;
for(int i = 1; i < num.length;i++){
if(major == num[i]){
count ++;
}
else if(count == 0){
count ++;
target = num[i];
}
else count --;
}
return target;
}
test case: {5，4，3，3，7，3，1，3，3} total: 9，length：9
| target | count | point to index (i) | point to value (num[i]) |
|---|---|---|---|
| 5 | 1 | 1 | 4 |
| 5 | 0 | 2 | 3 |
| 3 | 1 | 3 | 3 |
| 3 | 2 | 4 | 7 |
| 3 | 1 | 5 | 3 |
| 3 | 2 | 6 | 1 |
| 3 | 1 | 7 | 3 |
| 3 | 2 | 8 | 3 |
同樣的算法，下面這個(gè)代碼更好：
public int majorityElement(int[] nums) {
int target = 0, count = 0;
for (int num: nums) {
if (count == 0)
target = num; //每次target值被賦值替換完，下面的判斷直接進(jìn)行計(jì)數(shù)累加，0-->1
if (num != target)
count --;
else
count ++;
}
return target;
}
test case: {5，4，3，3，7，3，1，3，3} total: 9，length：9
| major | count | point to index (i) | point to value (num[i]) |
|---|---|---|---|
| 0 | 0 | 0 | 5 |
| 5 | 1 | 1 | 4 |
| 5 | 0 | 2 | 3 |
| 3 | 1 | 3 | 3 |
| 3 | 2 | 4 | 7 |
| 3 | 1 | 5 | 3 |
| 3 | 2 | 6 | 1 |
| 3 | 1 | 7 | 3 |
| 3 | 2 | 8 | 3 |
注：
兩個(gè)表格，得出的結(jié)果一樣，只不過(guò)起點(diǎn)不一樣。
表格前兩列是（再次）進(jìn)入for循環(huán)之前的值，后兩列是進(jìn)入for之后要與前兩列去比較的值，比較完之后，根據(jù)判斷語(yǔ)句得出的結(jié)果，寫入下一行的前兩列。
