[劍指offer題解][Java]陣列中出現次數超過一半的數字
最近看了好多資料結構文章，但是資料結構拾遺系列遲遲憋不出，主要原因是很多資料結構其實非常偏門，不僅日常很難遇到，學起來還涉及很多數學模型，很難有快速的理解方法。
本著女排“短平快”的精神，先更新下劍指offer題解系列。
眾所周知，《劍指offer》是一本“好書”。
為什麼這麼說？因為在面試老鳥眼裡，它裡面羅列的演算法題在面試中出現的頻率是非常非常高的。有多高，以我目前不多的面試來看，在所有遇到的演算法體中，本書演算法題出現的概率大概是60%，也就是10道題有6題是書中原題，如果把變種題目算上，那麼這個出現概率能到達90%。
如果你是個演算法菜雞（和我一樣），那麼最推薦的是先把劍指offer的題目搞明白。
對於劍指offer題解這個系列，我的寫作思路是，對於看過文章的讀者，能夠做到：
- 迅速瞭解該題常見解答思路（偏門思路不包括在內，節省大家時間，實在有研究需求的人可以查閱其它資料）
- 思路儘量貼近原書（例如書中提到的面試官經常會要求不改變原陣列，或者有空間限制等，儘量體現在程式碼中，保證讀者可以不漏掉書中細節）
- 儘量精簡話語，避免冗長解釋
- 給出程式碼可執行，註釋齊全，關注細節問題
題目介紹
陣列中有一個數字出現的次數超過陣列長度的一半，請找出這個數字。例如輸入一個長度為9的陣列{1,2,3,2,2,2,5,4,2}。由於數字2在陣列中出現了5次，超過陣列長度的一半，因此輸出2。如果不存在則輸出0。
解題思路
方法一
思路
該方法改變了原陣列。
首先要得到一個推論，那就是一旦有數字大於陣列的一半，那麼排序後的陣列的中位數肯定是這個數字，那麼我們就先找出這個數字。
這種演算法是受快速排序演算法的啟發。在隨機快速排序演算法中，我們現在陣列中隨機選擇一個數字，然後調整陣列中數字的順序，使得比選中的數字小的數字都排在它的左邊，比選中的數字大的數字都排在它的右邊。如果這個選中的數字的下標剛好是n/2，那麼這個數字就是陣列的中位數。如果它的下標大於n/2，那麼中位數應該位於它的左邊，我們可以接著在它的左邊部分的陣列中查詢。如果它的下標小於n/2，那麼中位數應該位於它的右邊，我們可以接著在它的右邊部分的陣列中查詢。這是一個典型的遞迴過程
找到這個數字後，再判斷他是否符合條件（大於陣列的一半），因為很有可能他是陣列中出現次數最多的，但是未必大於陣列的一半。
詳細細節見程式碼註釋。
程式碼
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length<=0) {
return 0;
}
int start = 0;
int length = array.length;
int end= length-1;
// 右移1位，相當於除2，效率更高
int middle = length>>1;
// 當前位置
int index = Partition(array,start,end);
// 直到取到中位數，才是結果
while(index!=middle){
if(index>middle){
index = Partition(array,start,index-1);
}
else{
index = Partition(array,index+1,end);
}
}
int result = array[middle];
// 需要統計該數字個數，必須要大於陣列長度的一半才能算
int times = 0;
for(int i=0;i<length;i++){
if(result==array[i]){
times++;
}
}
if(times*2 <= length){
result = 0;
}
return result;
}
// 快排中的每次排序實現，返回的是交換後start位置，也就是index一直改變的位置
private int Partition(int[] array,int start,int end){
// 取平均值不一定是整數，所以必須除2取整，不能右移
int flag = (array[start]+array[end])/2;
while(start<end){
while(array[end]>flag){
end--;
}
swap(array,start,end);
while(array[start]<=flag){
start++;
}
swap(array,start,end);
}
return start;
}
private void swap(int[] array, int num1, int num2){
int temp = array[num1];
array[num1] = array[num2];
array[num2] = temp;
}
}
複製程式碼
方法二：兩兩消除
思路
該方法不改變原陣列。
如果有符合條件的數字，則它出現的次數比其他所有數字出現的次數和還要多。 在遍歷陣列時儲存兩個值：
- times：次數
- result：當前數字
遍歷下一個數字時，若它與之前儲存的數字相同，則次數加1，否則次數減1；若次數為0，則儲存下一個數字，並將次數置為1。
遍歷結束後，所儲存的數字即為所求。
之後，還要再判斷它是否符合大於陣列的一半。
詳細細節見程式碼註釋。
程式碼
public int MoreThanHalfNum_Solution(int [] array) {
int length = array.length;
// 檢測陣列是否為空
if (length == 0){
return 0;
}
// 初始化result和times引數
int result = array[0];
int times = 1;
//遍歷陣列（由於初始化過，所以直接從第二個數字開始）
for(int i=1;i<length;i++){
// 次數為0時寫入下一個數字並將次數置1
if(times == 0){
result = array[i];
times = 1;
}
// 數字相同，加1
else if(array[i] == result){
times++;
}
// 數字不同，減1
else{
times--;
}
}
// 需要統計該數字個數，必須要大於陣列長度的一半才能算
times = 0;
for(int i=0;i<length;i++){
if(result==array[i]){
times++;
}
}
if(times*2 <= length){
result = 0;
}
return result;
}
複製程式碼
方法三：hashmap
思路
將陣列中的數字依次遍歷，並寫入hashmap中，hashmap的值是該數字出現的次數，並在每次迴圈中判斷是否該數次數大於陣列的一半，若有直接返回數字，否則遍歷完陣列返回0。