题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为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;}复制代码