原文链接: 何晓东 博客

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

数组中有一个数字呈现的次数超过数组长度的一半，请找出这个数字。
你能够假如数组是非空的，并且给定的数组总是存在少数元素。

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

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...

解题思路 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 官网题解

举荐个 算法面试通关40讲 优惠购买