Chapter3: 更好的查找與排序算法
7. 實戰(zhàn)解題：哪個數(shù)字重復數(shù)超過了數(shù)組一半長度腊尚？
題目
數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過了數(shù)組長度的一半消别，找出這個數(shù)字豪嗽。
算法
分析：因為這個數(shù)字k出現(xiàn)次數(shù)超過了N/2像寒，注意利用這個特性這意味著：
- 如果數(shù)組排好序的話疼邀，第N/2個元素一定是這個數(shù)字
- 這個數(shù)k的出現(xiàn)次數(shù)比所有其它元素加起來的還要多。
解法1
思路
hash統(tǒng)計陕凹，hashmap 沒學悍抑，之后再說
解法2
思路
排序后返回arr[N/2] 鳄炉，時間復雜度為快排的時間復雜度 O(nlgn)
解法3
思路
與上一題找k類似杜耙，其實不需要將全部數(shù)組排好序，進行一次快排的劃分即可拂盯，此時 arr[N/2] 即為所求的數(shù)佑女， 時間復雜度為 O(n)
快排的雙向掃描分區(qū)法的代碼參考上一篇文章
解法4
思路
如果一個數(shù)出現(xiàn)的次數(shù)超過數(shù)組一半的長度，那么就是說出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)還要多谈竿。
設置2個變量
value和count团驱，value代表元素的值，初始化為第一個元素值空凸，count代表某元素值的出現(xiàn)次數(shù)嚎花，初始化為1-
for循環(huán)遍歷數(shù)組，如果下一個元素的值與
value的值相同,則count++呀洲，否則count--, 當count==0時紊选，將value設置為下一個元素值并將count值設為1當count==0時，網(wǎng)上的代碼都是跳過了與
value使之為0的那個數(shù)道逗，將下下位賦值給value的比如數(shù)組里第一個數(shù)和第二個數(shù)不同的話兵罢，按照網(wǎng)上代碼的走法就會跳過第二個值，強迫癥的我感覺每個元素都要賦值給
value比較過才對滓窍，只需在if(count==0)的條件下卖词，i--回退一位即可至于為什么跳過也可以，以"第2個元素與第1個元素不同"這種情況來說吏夯，第2個元素使得
count變?yōu)?,即相當于第2個元素與第1個元素對消此蜈，如果按照網(wǎng)上的代碼跳過了第2個元素- 如果第2個元素是其它元素即横，則對結(jié)果沒有影響；
- 如果第2個元素就是要找的元素裆赵，因為要找的元素
k數(shù)量是大于N/2的令境，所以就算剛好只有[N/2]+1個，并且其它元素與k一一對消 ,與也會剩下一個k顾瞪，所以跳過對結(jié)果沒有影響
debug的過程真是艱辛啊┭┮﹏┭┮
因為要找的數(shù)字出現(xiàn)的次數(shù)比其他所有的數(shù)字出現(xiàn)的次數(shù)之和要大舔庶，所以遍歷完數(shù)組，最后必然
count>=1陈醒， 并且value的值就是要找的值
代碼
int findK(int* arr,int arrLen){
int value=arr[0];
int count=1;
for(int i=1;i<arrLen;i++){
if(count==0){
i--;//避免value的賦值跳過那個使count等于0的與value比較的數(shù)組元素 ,網(wǎng)上其它人的代碼就是少了這條語句
value=arr[i];
count++;
}
else{
if(value==arr[i])//count!=0 && value==arr[i]
count++;
else//count!=0&value!=arr[i]
count--;
}
}
return value;
}
debug過程記錄
一開始發(fā)現(xiàn)網(wǎng)上的代碼是跳過之后惕橙，也沒有仔細思考可行性，就試著驗證一下把第2個元素設置為要找的值 k 钉跷，結(jié)果出錯了弥鹦，找了另一個出現(xiàn)次數(shù)比 k 少1次的數(shù)，就以為自己的想法是正確的爷辙，因為跳過了一個k 值
于是就額外寫了個判斷語句彬坏，使得不跳過第二個數(shù)，運行結(jié)果就正確了膝晾，科十自己又想栓始，跳過也不是只是第二個數(shù)跳過啊，自己在腦海里演練了一下血当，發(fā)現(xiàn)使得 count==0 的那個數(shù)組元素在賦值給 value 時都會被跳過幻赚，這就說不通了，那就應該在if(count==0) 里面改臊旭，改了又有bug!!
在網(wǎng)上找了兩篇博客落恼，這一思路的寫法都是那樣跳過的，但是驗證又有問題离熏，差點要放棄佳谦，找第三篇博客的時候， 看到別人還寫了驗證輸入數(shù)組是否存在數(shù)量超過長度一般的數(shù)的代碼滋戳，忽然發(fā)現(xiàn)自己之前自己設置的數(shù)組中重復數(shù)最高的數(shù)沒有超過數(shù)組長度的一半Ｗ昝铩！所以才會報錯胧瓜！于是把數(shù)組修正過來矢棚，網(wǎng)上的代碼就不報錯了！但是自己的代碼還是有錯府喳，正百思不得其解的時候忽然想到 value=arr[i--]; 這種寫法是先賦值蒲肋，i 再-1，修正為 [--i] 就沒問題了
擴展：加強版水王問題
問題
我們知道，水王問題：有N個數(shù)兜粘，其中有一個數(shù)出現(xiàn)超過一半申窘，要求在線性時間求出這個數(shù)。(就是上面解決的問題)
加強版水王：有N個數(shù)孔轴，其中有一個數(shù)剛好出現(xiàn)一半次數(shù)剃法，要求在線性時間內(nèi)求出這個數(shù)。
思路
仔細分析的話路鹰，占一半的數(shù)字贷洲，只能在兩個變量中出現(xiàn)：value 和數(shù)組最后一個元素arr[arrLen-1]。只需要在遍歷數(shù)組的時候統(tǒng)計最后一個變量arr[arrLen-1] 的出現(xiàn)次數(shù)即可晋柱，如果=arrLen/2 优构，則它就是要找的元素，否則 value 就是
代碼
int findK(int* arr,int arrLen){
int value=arr[0];
int count=1;
int countOfLast=0;//統(tǒng)計最后的元素arr[n-1]出現(xiàn)的個數(shù)
for(int i=1;i<arrLen;i++){
//增加最后一個元素的計數(shù)步驟
if(arr[i]==arr[arrLen-1])
countOfLast++;
if(count==0){
i--;//避免value的賦值跳過那個使count等于0的與value比較的數(shù)組元素
value=arr[i];
count++;
}
else{
if(value==arr[i])//count!=0 && value==arr[i]
count++;
else//count!=0&value!=arr[i]
count--;
}
}
//增加最后一個元素的計數(shù)步驟
if(arr[0]=arr[arrLen-1])
countOfLast++;
//如果最后一個元素出現(xiàn)次數(shù)是n/2,則這個元素就是要找的數(shù)
if(countOfLast==arrLen/2)
return arr[arrLen-1];
else
return value;
}
參考資料
[1] 一個數(shù)組中有一個數(shù)字的次數(shù)超過了數(shù)組的一半
[2] 加強版水王：找出出現(xiàn)次數(shù)剛好是一半的數(shù)字
l
