2020-08-19-PHP 计算数组中出现次数超过一半的数字

layout: posttitle: PHP 计算数组中出现次数超过一半的数字
subtitle: PHP 计算数组中出现次数超过一半的数字
date: 2020-08-19
author: he xiaodong
header-img: img/default-post-bg.jpg
catalog: true
tags:
- Go
- PHP
- LeetCode
- 次数超过一半的数字
- 多数元素

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

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof

解题思路 1

类似 array_count_values 函数的功能而已

代码

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function majorityElement($nums) {
        $halfLength = floor(count($nums) / 2);
        $check = [];
        foreach ($nums as $item) {
            if ($check[$item] > $halfLength) {
                return $item;
            }
            $check[$item] += 1;
        }
    }
}

解题思路 2 - 摩尔投票法

摩尔投票算法(Boyer–Moore majority vote algorithm)，是一个在O(n)的时间复杂度和O(1)的空间复杂度下寻找线性表中出现一半以上元素的算法，采用流的思想处理数据。

场景： 如何在任意多的候选人（选票无序），选出获得票数具有压倒性优势的的那个？（此人得票超过其他所有人之和，即占1/2以上）。

当选票有序时，这个问题非常简单，因为整个线性表的中位数必定在长度超过1/2的段中：段在开头，则段尾一定超过1/2，段在结尾，则段头一定小于1/2。我们只需要检查线性表的中位数即可得到结果，时间复杂度为O(1)。

当选票无序时，想采用这种方法则必须对线性表进行排序，时间复杂度就会增长到所采用排序算法的时间复杂度。

那么有没有办法只顺序访问一遍线性表就能获得答案的方法呢？那就是摩尔投票法。

原理： 摩尔算法的核心思想是任意元素两两抵消，最后剩下的元素一定是出现次数超过1/2的，算法维护一个序列元素num和一个计数器，num指示当前数字，计数器指示此元素还可以抵消几个元素。

代码

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function majorityElement($nums) {
        $votes = 0;
        foreach ($nums as $num) {
            if($votes == 0) $x = $num;
            $votes += $num == $x ? 1 : -1;
        }
        return $x;
    }
}

参考链接

1. 摩尔投票算法（双角度理解）
2. leetcode 官方题解

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券