《剑指Offer》-39.数组中出现次数超过一半的数字

题干

数组中有一个数字出现的册书超过数组长度的一半，请找出这个数字。例如，输入一个长度为9的数组「1，2，3，2，2，2，5，4，2」。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2.

解题思路

数组中有一个数字出现的次数超过数组长度的一半，说明它出现的次数比其他所有数字出现次数的和还要多。因此，我们可以考虑在遍历数组的时候保存两个值：一个是数组中一个数字，另一个是次数。当遍历到下一个数字的时候，如果下个数字和之前保存的数组相同则次数加1，否则次数减1，如果次数为0，则保存下一个数字并将次数设为1，直到遍历结束时保存的数字就是所求的数字。

代码实现

<?php
function moreThanHalfNumber($numbers)
{
    if (empty($numbers)) {
        return -1;
    }

    $len = count($numbers);
    $res = $numbers[0];
    $times = 1;
    for ($i = 1; $i < $len; $i++) {
        if ($times == 0) {
            $res = $numbers[$i];
            $times = 1;
        } elseif ($res == $numbers[$i]) {
            $times++;
        } else {
            $times--;
        }
    }

    $times = 0;
    for ($i = 0; $i < $len; $i++) {
        if ($numbers[$i] == $res) {
            $times++;
        }
    }

    if ($times << 1 <= $len) {
        return -1;
    }

    return $res;
}
echo moreThanHalfNumber([1,2,2,2,3]); // 2
echo moreThanHalfNumber([1,2,2,3,3,4]); // -1