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)一個數(shù)之前不在map里
myMap.put(num, 1); //放進(jìn)去 <原值，計數(shù)>
else
myMap.put(num, myMap.get(num)+1); //如果存在，計數(shù)+1
if (myMap.get(num)>nums.length/2) {
target = num;
break; //不一定traverse整個nums，也許結(jié)果就出來了
}
}
return target;
}
Boyer–Moore majority vote algorithm
基本思路：最初設(shè)置兩個值，一個target压昼，一個count，分別進(jìn)行統(tǒng)計。target從選取nums[0]開始尸执，每當(dāng)計數(shù)變成0的時候，target值就會換缓醋。其實可以按“消除”的想法去理解如失，比如target值是3，連續(xù)出現(xiàn)了四次送粱，那么這個時候count=4褪贵，但是連續(xù)又連續(xù)出現(xiàn)了五次不是3的值，那么count不僅被清0了抗俄，而且target的值也被替換了脆丁，從新開始統(tǒng)計。到最后动雹，都“消除”完了槽卫，還能成為target，說明具有數(shù)量上的優(yōu)勢胰蝠，也就是我們要找的“大量”歼培、“總數(shù)過半”的值震蒋。
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 |
同樣的算法，下面這個代碼更好：
public int majorityElement(int[] nums) {
int target = 0, count = 0;
for (int num: nums) {
if (count == 0)
target = num; //每次target值被賦值替換完丐枉，下面的判斷直接進(jìn)行計數(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 |
注：
兩個表格，得出的結(jié)果一樣椅挣，只不過起點不一樣头岔。
表格前兩列是（再次）進(jìn)入for循環(huán)之前的值，后兩列是進(jìn)入for之后要與前兩列去比較的值鼠证，比較完之后峡竣，根據(jù)判斷語句得出的結(jié)果，寫入下一行的前兩列量九。
