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;
}
}
参考链接