【刷算法】數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

Lin_R 發(fā)布于2019-08-23 10:27 / 1690人閱讀

摘要：題目描述數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。如果不存在則輸出。分析像這樣的數(shù)組，如果每次去掉兩個不同的數(shù)字，那么到最后會剩下，就是數(shù)組中超過一半的數(shù)字。可以使用代碼來模擬這個過程即可。

題目描述

數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半，因此輸出2。如果不存在則輸出0。

分析

像[1,2,3,2,2,2,5,4,2]這樣的數(shù)組，如果每次去掉兩個不同的數(shù)字，那么到最后會剩下[2]，2就是數(shù)組中超過一半的數(shù)字。可以使用代碼來模擬這個過程即可。

代碼實現(xiàn)

function MoreThanHalfNum_Solution(numbers)
{
    if(numbers.length === 0)
        return 0;
    if(numbers.length === 1)
        return numbers[0];
    
    var times = 0, cand;
    
    for(var i = 0;i < numbers.length;i++) {
        if(times === 0){
            cand = numbers[i];
            times = 1;
        } else {
            if(cand === numbers[i])  
                times++;
            else 
                times--;
        }
    }
    
    times = 0;
    for(var i = 0;i < numbers.length;i++) {
        if(cand === numbers[i])
            times++;
    }
    if(times > Math.floor(numbers.length/2))
        return cand;
    else
        return 0;
}

GPU云服務(wù)器云服務(wù)器數(shù)組中未出現(xiàn)的數(shù)字數(shù)組中出現(xiàn)多次數(shù)據(jù)出現(xiàn)次數(shù)統(tǒng)計 php統(tǒng)計出現(xiàn)次數(shù)

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/96362.html

相關(guān)文章

劍指offer中的算法題(PHP版)

摘要：二維數(shù)組中的查找在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。解法有兩種，一種是遞歸法，一種是迭代法但是遞歸法計算的時間復(fù)雜度是以的指數(shù)的方式遞增的，如果面試中千萬不要用遞歸法，一定要用迭代法。二維數(shù)組中的查找在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和...

big_cat 2019-06-27 15:43 評論0 收藏0
面試題39：數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

摘要：面試題數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，找出這個數(shù)字。面試題39：數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)...

Eminjannn 2021-11-15 11:38 評論0 收藏0
??思維導(dǎo)圖整理大廠面試高頻數(shù)組9: 刪除重復(fù)元素的通解問題, 力扣26/80??

此專欄文章是對力扣上算法題目各種方法的總結(jié)和歸納, 整理出最重要的思路和知識重點并以思維導(dǎo)圖形式呈現(xiàn), 當然也會加上我對導(dǎo)圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復(fù)看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經(jīng)知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據(jù)題號先去力扣看看官方題解, 然后再看本文內(nèi)容). 關(guān)...

MasonEast 2021-09-04 16:40 評論0 收藏0
【刷算法】整數(shù)中1出現(xiàn)的次數(shù)（從1到n整數(shù)中1出現(xiàn)的次數(shù)）

摘要：題目描述求出的整數(shù)中出現(xiàn)的次數(shù)并算出的整數(shù)中出現(xiàn)的次數(shù)為此他特別數(shù)了一下中包含的數(shù)字有因此共出現(xiàn)次但是對于后面問題他就沒轍了。希望你們幫幫他并把問題更加普遍化可以很快的求出任意非負整數(shù)區(qū)間中出現(xiàn)的次數(shù)從到中出現(xiàn)的次數(shù)。題目描述求出1~13的整數(shù)中1出現(xiàn)的次數(shù),并算出100~1300的整數(shù)中1出現(xiàn)的次數(shù)？為此他特別數(shù)了一下1~13中包含1的數(shù)字有1、10、11、12、13因此共出現(xiàn)6...

Shisui 2019-08-23 10:29 評論0 收藏0
一道有意思的面試算法題

摘要：解決方案異或操作異或運算是對于二進制數(shù)字而言的，比如說一個有兩個二進制，如果兩個值不相同，則異或結(jié)果為。比如說，本質(zhì)上其實是和的每一對比特位執(zhí)行異或操作，等價于下面數(shù)字對應(yīng)的二進制數(shù)字對應(yīng)的二進制數(shù)字對應(yīng)的二進制因此的結(jié)果就為啦。新年第一篇文章，先祝大家新年快樂！！那么接下來進入正文。前言前陣子突發(fā)奇想，突然開始刷leetcode。其中刷到了一道有意思的題目，發(fā)現(xiàn)這道題是當時秋招...

maxmin 2019-08-23 14:28 評論0 收藏0