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

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

摘要：題目描述數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半，請(qǐng)找出這個(gè)數(shù)字。如果不存在則輸出。分析像這樣的數(shù)組，如果每次去掉兩個(gè)不同的數(shù)字，那么到最后會(huì)剩下，就是數(shù)組中超過(guò)一半的數(shù)字?？梢允褂么a來(lái)模擬這個(gè)過(guò)程即可。

題目描述

數(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。

分析

像[1,2,3,2,2,2,5,4,2]這樣的數(shù)組，如果每次去掉兩個(gè)不同的數(shù)字，那么到最后會(huì)剩下[2]，2就是數(shù)組中超過(guò)一半的數(shù)字?？梢允褂么a來(lái)模擬這個(gè)過(guò)程即可。

代碼實(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)計(jì) php統(tǒng)計(jì)出現(xiàn)次數(shù)

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/96362.html

相關(guān)文章

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

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

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

摘要：面試題數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字?jǐn)?shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半，找出這個(gè)數(shù)字。面試題39：數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)...

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

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

MasonEast 2021-09-04 16:40 評(píng)論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)次但是對(duì)于后面問題他就沒轍了。希望你們幫幫他并把問題更加普遍化可以很快的求出任意非負(fù)整數(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 評(píng)論0 收藏0
一道有意思的面試算法題

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

maxmin 2019-08-23 14:28 評(píng)論0 收藏0