前言
最近看了好多數(shù)據(jù)結(jié)構(gòu)文章套么，但是數(shù)據(jù)結(jié)構(gòu)拾遺系列遲遲憋不出蟹漓，主要原因是很多數(shù)據(jù)結(jié)構(gòu)其實(shí)非常偏門最蕾，不僅日常很難遇到依溯，學(xué)起來(lái)還涉及很多數(shù)學(xué)模型，很難有快速的理解方法瘟则。
本著女排“短平快”的精神黎炉，先更新下劍指offer題解系列。
眾所周知醋拧，《劍指offer》是一本“好書(shū)”慷嗜。
為什么這么說(shuō)？因?yàn)樵诿嬖嚴(yán)哮B(niǎo)眼里丹壕，它里面羅列的算法題在面試中出現(xiàn)的頻率是非常非常高的庆械。有多高，以我目前不多的面試來(lái)看菌赖，在所有遇到的算法體中缭乘，本書(shū)算法題出現(xiàn)的概率大概是60%，也就是10道題有6題是書(shū)中原題琉用，如果把變種題目算上堕绩，那么這個(gè)出現(xiàn)概率能到達(dá)90%。
如果你是個(gè)算法菜雞（和我一樣）邑时，那么最推薦的是先把劍指offer的題目搞明白奴紧。
對(duì)于劍指offer題解這個(gè)系列，我的寫(xiě)作思路是晶丘，對(duì)于看過(guò)文章的讀者黍氮，能夠做到：
- 迅速了解該題常見(jiàn)解答思路（偏門思路不包括在內(nèi)，節(jié)省大家時(shí)間浅浮，實(shí)在有研究需求的人可以查閱其它資料）
- 思路盡量貼近原書(shū)（例如書(shū)中提到的面試官經(jīng)常會(huì)要求不改變?cè)瓟?shù)組滤钱，或者有空間限制等，盡量體現(xiàn)在代碼中脑题，保證讀者可以不漏掉書(shū)中細(xì)節(jié)）
- 盡量精簡(jiǎn)話語(yǔ)件缸，避免冗長(zhǎng)解釋
- 給出代碼可運(yùn)行，注釋齊全叔遂，關(guān)注細(xì)節(jié)問(wèn)題
題目介紹
數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半他炊，請(qǐng)找出這個(gè)數(shù)字争剿。例如輸入一個(gè)長(zhǎng)度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次痊末，超過(guò)數(shù)組長(zhǎng)度的一半蚕苇，因此輸出2。如果不存在則輸出0凿叠。
解題思路
方法一
思路
該方法改變了原數(shù)組涩笤。
首先要得到一個(gè)推論，那就是一旦有數(shù)字大于數(shù)組的一半盒件，那么排序后的數(shù)組的中位數(shù)肯定是這個(gè)數(shù)字蹬碧，那么我們就先找出這個(gè)數(shù)字。
這種算法是受快速排序算法的啟發(fā)炒刁。在隨機(jī)快速排序算法中恩沽，我們現(xiàn)在數(shù)組中隨機(jī)選擇一個(gè)數(shù)字，然后調(diào)整數(shù)組中數(shù)字的順序翔始，使得比選中的數(shù)字小的數(shù)字都排在它的左邊罗心，比選中的數(shù)字大的數(shù)字都排在它的右邊。如果這個(gè)選中的數(shù)字的下標(biāo)剛好是n/2城瞎，那么這個(gè)數(shù)字就是數(shù)組的中位數(shù)渤闷。如果它的下標(biāo)大于n/2，那么中位數(shù)應(yīng)該位于它的左邊脖镀，我們可以接著在它的左邊部分的數(shù)組中查找肤晓。如果它的下標(biāo)小于n/2，那么中位數(shù)應(yīng)該位于它的右邊认然，我們可以接著在它的右邊部分的數(shù)組中查找。這是一個(gè)典型的遞歸過(guò)程
找到這個(gè)數(shù)字后漫萄，再判斷他是否符合條件（大于數(shù)組的一半）卷员，因?yàn)楹苡锌赡芩菙?shù)組中出現(xiàn)次數(shù)最多的，但是未必大于數(shù)組的一半腾务。
詳細(xì)細(xì)節(jié)見(jiàn)代碼注釋毕骡。
代碼
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位，相當(dāng)于除2岩瘦，效率更高
int middle = length>>1;
// 當(dāng)前位置
int index = Partition(array,start,end);
// 直到取到中位數(shù)未巫，才是結(jié)果
while(index!=middle){
if(index>middle){
index = Partition(array,start,index-1);
}
else{
index = Partition(array,index+1,end);
}
}
int result = array[middle];
// 需要統(tǒng)計(jì)該數(shù)字個(gè)數(shù)，必須要大于數(shù)組長(zhǎng)度的一半才能算
int times = 0;
for(int i=0;i<length;i++){
if(result==array[i]){
times++;
}
}
if(times*2 <= length){
result = 0;
}
return result;
}
// 快排中的每次排序?qū)崿F(xiàn)启昧，返回的是交換后start位置叙凡，也就是index一直改變的位置
private int Partition(int[] array,int start,int end){
// 取平均值不一定是整數(shù)，所以必須除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;
}
}
方法二：兩兩消除
思路
該方法不改變?cè)瓟?shù)組握爷。
如果有符合條件的數(shù)字跛璧，則它出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)和還要多。
在遍歷數(shù)組時(shí)保存兩個(gè)值：
- times：次數(shù)
- result：當(dāng)前數(shù)字
遍歷下一個(gè)數(shù)字時(shí)新啼，若它與之前保存的數(shù)字相同追城，則次數(shù)加1，否則次數(shù)減1燥撞；若次數(shù)為0座柱，則保存下一個(gè)數(shù)字，并將次數(shù)置為1物舒。
遍歷結(jié)束后色洞，所保存的數(shù)字即為所求。
之后茶鉴，還要再判斷它是否符合大于數(shù)組的一半锋玲。
詳細(xì)細(xì)節(jié)見(jiàn)代碼注釋。
代碼
public int MoreThanHalfNum_Solution(int [] array) {
int length = array.length;
// 檢測(cè)數(shù)組是否為空
if (length == 0){
return 0;
}
// 初始化result和times參數(shù)
int result = array[0];
int times = 1;
//遍歷數(shù)組（由于初始化過(guò)涵叮，所以直接從第二個(gè)數(shù)字開(kāi)始）
for(int i=1;i<length;i++){
// 次數(shù)為0時(shí)寫(xiě)入下一個(gè)數(shù)字并將次數(shù)置1
if(times == 0){
result = array[i];
times = 1;
}
// 數(shù)字相同惭蹂，加1
else if(array[i] == result){
times++;
}
// 數(shù)字不同，減1
else{
times--;
}
}
// 需要統(tǒng)計(jì)該數(shù)字個(gè)數(shù)割粮，必須要大于數(shù)組長(zhǎng)度的一半才能算
times = 0;
for(int i=0;i<length;i++){
if(result==array[i]){
times++;
}
}
if(times*2 <= length){
result = 0;
}
return result;
}
方法三：hashmap
思路
將數(shù)組中的數(shù)字依次遍歷盾碗，并寫(xiě)入hashmap中，hashmap的值是該數(shù)字出現(xiàn)的次數(shù)舀瓢，并在每次循環(huán)中判斷是否該數(shù)次數(shù)大于數(shù)組的一半廷雅，若有直接返回?cái)?shù)字，否則遍歷完數(shù)組返回0京髓。
代碼
思路簡(jiǎn)單航缀，代碼略。
總結(jié)
三種方法時(shí)間復(fù)雜度都是O（n）
