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

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

author: he xiaodong date: 2020-08-19
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 官方题解

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