数组中出现次数超过一半的数字

题目描述

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

解法一：array_count_values()

用 php 的函数 array_count_values()可以很简单的算出来。

public function php_method($numbers)
{
    $count  = array_count_values($numbers); // 统计数组中所有的值出现的次数
    $length = count($numbers);

    foreach ($count as $k => $v) {
        if ($v > ($length/2)) return $k;
    }

    return 0;
}

解法二：摩尔投票法

摩尔投票法说明：
假设数组第一个元素1是我们要找的数，其票数为1，那么其余不等于1的元素的票数都为-1。由于我们要找的数出现的次数超过一半，那么最终数组的票数总和一定是大于0。

例如，数组[4, 2, 1, 4, 2, 4]，运用摩尔投票法的步骤说明：

1. 把要找的数$target初始化为数组第一个元素（即4），总票数$votes初始化为（即1）。
2. 与第二个元素（即2）比较。如果相等，总票数+1，继续遍历数组;如果不相等，总票数-1，继续遍历数组。
3. 如果总票数=0，则将 $target 等于下一个元素（即1），$votes = 1。
4. 继续重复步骤2，与下一个元素比较。
5. 摩尔投票法是假设了数组一定会有一个数超过数组长度的一半，但这道题可能不存在这个数，所以需要在最后验证出现的次数是否超过数组长度的一半。

<?php

namespace app\index\controller;

class Index
{
    /**
     * 查找
     */
    function MoreThanHalfNum_Solution($numbers)
    {
        if (empty($numbers)) return;

        $length = count($numbers); // 数组长度
        $target = $numbers[0];     // 目标值：初始化为数组第一个元素
        $votes  = 1;               // 总票数初始值

        for ($i = 1; $i < $length; $i++) {                 // 循环数组
            $numbers[$i] == $target ? $votes++ : $votes--; // 比较两数是否相等
            if ($votes == 0 && $i + 1< $length) {          // 如果总票数为0，重新选择 $target
                $i++;
                $target = $numbers[$i];
                $votes = 1;
            }
        }

        // 最后需要验证是否符合条件
        $time = 0;
        foreach ($numbers as $k) {
            if ($k == $target) $time++;
        }
        return $time > ($length/2) ? $first : 0;
    }
}

   /**
     * 测试
     */
    public function test()
    {
        $numbers = [4, 2, 1, 4, 2, 4];
        $this->MoreThanHalfNum_Solution($numbers); // 调用函数
    }