【刷算法】數組中出現次數超過一半的數字

Lin_R 發布于2019-08-23 10:27 / 1639人閱讀

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

題目描述

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

分析

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

代碼實現

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云服務器數組中未出現的數字數組中出現多次數據出現次數統計 php統計出現次數

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/96362.html

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

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

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

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

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

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

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

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

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

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

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