2019-1-8 吴亲库里 库里的深夜食堂
给这道题超级有意思。给定n个数的数组。找出数组元素中出现次数超过 n/3 次的元素。难点来了，只能在 O(n) 的时间复杂度和 O(1) 的空间复杂度完成.
这道题数学不好是完全没有思路的，解法叫摩尔投票法(具体可以自行了解)。在开始之前，我们需要明白一个道理。即任意一个 n 元素的数组，最多只能有两个元素出现的次数 超过 n/3 。为什么呢。可以使用反证法。假设现在一个 n 个元素的数组有三个元素出现的次数大于 n/3。那么这个数组中的个数一定大于 3(n/3)，与原数组 n 个相悖。确定了最多只有两个之后，可以开始选两个候选人了。第一遍就是确定两个候选的值。第二遍就是实际检测候选数是否真的满足条件。具体看代码，如果觉得难以理解。一个简单的方法就是自己拿笔实现这个过程。*
/**
* @param Integer[] $nums
* @return Integer[]
*/
function majorityElement($nums) {
$num=count($nums);
$c1=0;
$c2=0;
$m1=null;
$m2=null;
for($i=0;$i<$num;$i++){
if(isset($m1) && $nums[$i]==$m1) $c1++;
else if(isset($m2) && $nums[$i] ==$m2){
$c2++;
}
else if($c1==0){
$c1=1;
$m1=$nums[$i];
}
else if($c2==0){
$c2=1;
$m2=$nums[$i];
}
else {
$c1--;
$c2--;
}
}
$c1=0;
$c2=0;
for($i=0;$i<$num;$i++){
if(isset($m1) && $nums[$i]==$m1) $c1++;
if(isset($m2) && $nums[$i]==$m2) $c2++;
}
$res=[];
if($c1>$num/3) $res[]=$m1;
if($c2>$num/3) $res[]=$m2;
return $res;
}还有一点要提的，我把具体的场景再复现一下。你可以注意到我现在使用的是 isset,而不是 $m1 !=null (虽然这是个微不足道的问题，但是还是提一下)。为什么？因为在 php 中 null 和 0 值是相等的!! 只是类型不同。php 中的变量在底层都是 c 语言的结构体存储的。空字符串,null ，false 都是用 0 存储的。所以日常 0==null 返回的是true, 0===null 才会返回false。
