乐趣区

关于php:leetcode-39169PHP-计算数组中出现次数超过一半的数字

jiezi

原文链接: 何晓东 博客

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 讲 优惠购买

退出移动版