Chapter3: 更好的查找與排序算法

7. 實(shí)戰(zhàn)解題：哪個(gè)數(shù)字重復(fù)數(shù)超過了數(shù)組一半長度？

題目

數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過了數(shù)組長度的一半，找出這個(gè)數(shù)字。

算法

分析：因?yàn)檫@個(gè)數(shù)字k出現(xiàn)次數(shù)超過了N/2，注意利用這個(gè)特性這意味著：

• 如果數(shù)組排好序的話，第N/2個(gè)元素一定是這個(gè)數(shù)字
• 這個(gè)數(shù)k的出現(xiàn)次數(shù)比所有其它元素加起來的還要多。

解法1

思路

hash統(tǒng)計(jì)，hashmap 沒學(xué)，之后再說

解法2

思路

排序后返回arr[N/2] ，時(shí)間復(fù)雜度為快排的時(shí)間復(fù)雜度 O(nlgn)

解法3

思路

與上一題找k類似，其實(shí)不需要將全部數(shù)組排好序，進(jìn)行一次快排的劃分即可，此時(shí) arr[N/2] 即為所求的數(shù)， 時(shí)間復(fù)雜度為 O(n)

快排的雙向掃描分區(qū)法的代碼參考上一篇文章

解法4

思路

如果一個(gè)數(shù)出現(xiàn)的次數(shù)超過數(shù)組一半的長度，那么就是說出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)還要多。

• 設(shè)置2個(gè)變量 value 和 count ，value 代表元素的值，初始化為第一個(gè)元素值，count 代表某元素值的出現(xiàn)次數(shù)，初始化為1

• for循環(huán)遍歷數(shù)組，如果下一個(gè)元素的值與 value 的值相同,則 count++ ，否則count-- , 當(dāng)count==0 時(shí)，將value 設(shè)置為下一個(gè)元素值并將count值設(shè)為1

  當(dāng)count==0時(shí)，網(wǎng)上的代碼都是跳過了與 value使之為0的那個(gè)數(shù)，將下下位賦值給 value 的

  比如數(shù)組里第一個(gè)數(shù)和第二個(gè)數(shù)不同的話，按照網(wǎng)上代碼的走法就會(huì)跳過第二個(gè)值，強(qiáng)迫癥的我感覺每個(gè)元素都要賦值給 value 比較過才對(duì)，只需在 if(count==0) 的條件下，i-- 回退一位即可

  至于為什么跳過也可以，以"第2個(gè)元素與第1個(gè)元素不同"這種情況來說，第2個(gè)元素使得 count變?yōu)?,即相當(dāng)于第2個(gè)元素與第1個(gè)元素對(duì)消，如果按照網(wǎng)上的代碼跳過了第2個(gè)元素

  • 如果第2個(gè)元素是其它元素，則對(duì)結(jié)果沒有影響；
  • 如果第2個(gè)元素就是要找的元素，因?yàn)橐业脑?k 數(shù)量是大于N/2的，所以就算剛好只有[N/2]+1個(gè)，并且其它元素與 k一一對(duì)消 ,與也會(huì)剩下一個(gè)k，所以跳過對(duì)結(jié)果沒有影響

  debug的過程真是艱辛啊┭┮﹏┭┮

• 因?yàn)橐业臄?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的賦值跳過那個(gè)使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)上的代碼是跳過之后，也沒有仔細(xì)思考可行性，就試著驗(yàn)證一下把第2個(gè)元素設(shè)置為要找的值 k ，結(jié)果出錯(cuò)了，找了另一個(gè)出現(xiàn)次數(shù)比 k 少1次的數(shù)，就以為自己的想法是正確的，因?yàn)樘^了一個(gè)k 值

于是就額外寫了個(gè)判斷語句，使得不跳過第二個(gè)數(shù)，運(yùn)行結(jié)果就正確了，科十自己又想，跳過也不是只是第二個(gè)數(shù)跳過啊，自己在腦海里演練了一下，發(fā)現(xiàn)使得 count==0 的那個(gè)數(shù)組元素在賦值給 value 時(shí)都會(huì)被跳過，這就說不通了，那就應(yīng)該在if(count==0) 里面改，改了又有bug!!

在網(wǎng)上找了兩篇博客，這一思路的寫法都是那樣跳過的，但是驗(yàn)證又有問題，差點(diǎn)要放棄，找第三篇博客的時(shí)候， 看到別人還寫了驗(yàn)證輸入數(shù)組是否存在數(shù)量超過長度一般的數(shù)的代碼，忽然發(fā)現(xiàn)自己之前自己設(shè)置的數(shù)組中重復(fù)數(shù)最高的數(shù)沒有超過數(shù)組長度的一半！！所以才會(huì)報(bào)錯(cuò)！于是把數(shù)組修正過來，網(wǎng)上的代碼就不報(bào)錯(cuò)了！但是自己的代碼還是有錯(cuò)，正百思不得其解的時(shí)候忽然想到 value=arr[i--]; 這種寫法是先賦值，i 再-1，修正為 [--i] 就沒問題了

擴(kuò)展：加強(qiáng)版水王問題

問題

我們知道，水王問題：有N個(gè)數(shù)，其中有一個(gè)數(shù)出現(xiàn)超過一半，要求在線性時(shí)間求出這個(gè)數(shù)。(就是上面解決的問題)

加強(qiáng)版水王：有N個(gè)數(shù)，其中有一個(gè)數(shù)剛好出現(xiàn)一半次數(shù)，要求在線性時(shí)間內(nèi)求出這個(gè)數(shù)。

思路

仔細(xì)分析的話，占一半的數(shù)字，只能在兩個(gè)變量中出現(xiàn)：value 和數(shù)組最后一個(gè)元素arr[arrLen-1]。只需要在遍歷數(shù)組的時(shí)候統(tǒng)計(jì)最后一個(gè)變量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)計(jì)最后的元素arr[n-1]出現(xiàn)的個(gè)數(shù) 
        
    for(int i=1;i<arrLen;i++){
        
        //增加最后一個(gè)元素的計(jì)數(shù)步驟
        if(arr[i]==arr[arrLen-1]) 
            countOfLast++;
        
        if(count==0){
            i--;//避免value的賦值跳過那個(gè)使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--;
        }
    }
    
    //增加最后一個(gè)元素的計(jì)數(shù)步驟
    if(arr[0]=arr[arrLen-1])
        countOfLast++;
    //如果最后一個(gè)元素出現(xiàn)次數(shù)是n/2,則這個(gè)元素就是要找的數(shù) 
    if(countOfLast==arrLen/2)
        return arr[arrLen-1];
    else
        return value;
}

參考資料

[1] 一個(gè)數(shù)組中有一個(gè)數(shù)字的次數(shù)超過了數(shù)組的一半

[2] 加強(qiáng)版水王：找出出現(xiàn)次數(shù)剛好是一半的數(shù)字

l