第39题 – 数组中出现次数超过一半的数字

作者: 周伟林 分类: 剑指offer 发布时间: 2018-05-23 11:27

牛客链接

题目描述

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

解题思路

如果某个数字出现次数超过一半,要么完全夹住其他的数字,要么有两个一样的数相邻。利用此规律,cnt。
遍历一遍,用cnt计数。

JavaScript实现

function MoreThanHalfNum_Solution(numbers)
{
    let len = numbers.length;
    if(len === 0) return 0;
    
    let num = numbers[0], cnt = 1;
    for(let i = 1; i < len; ++i){
        numbers[i] === num ? ++cnt: --cnt;
        if(cnt === 0){
            cnt = 1;
            num = numbers[i];
        }
    }
    // 检测是否恰好是最后一个数,且数组长度大于1
    if(len > 1 && cnt === 1 && num === numbers[len-1]){
        num = 0;
    }
    return num;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注