2019-03-25 吴亲库里 库里的深夜食堂
给你一个整数数组，找出多数元素，多数元素表示出现的次数超过数组的二分之一。
题目已经说明，你可以假设这不是一个空数组，并且一定存在多数元素，我们可以这样，循环整个数组，记录下每一个数组出现的次数，然后进行判断元素出现的次数大于1/2,那么直接返回这个数。
/**
* @param Integer[] $nums
* @return Integer
*/
function majorityElement($nums) {
$data=[];
for($i=0;$i<count($nums);$i++) {
$data[$nums[$i]]=$data[$nums[$i]]+1 ;
if($data[$nums[$i]] >(count($nums) /2)){
return $nums[$i];
}
}
}我们也可以这样解，这是一个求众数（即上面所称呼的多数元素）的问题，有一种叫做摩尔投票法（Google一下）适合解这类题目。我们可以先将第一个数当成众数，然后设置计数器等于1，如果当前的数和众数等值，那么计数器加1，否则计数器减去1，如果计数器等于0的话，说明当前还不是众数的个数都和众数的个数相同了，那么我们就需要更换众数了，如果我们更换了众数，但是后面当前更换的众数又大量出现，那么他就重新变成了众数，直到验证完毕。求出众数。
/**
* @param Integer[] $nums
* @return Integer
*/
function majorityElement($nums) {
$count=1;
$current=$nums[0];
for($i=1;$i<count($nums);$i++){
$val=$nums[$i];
if($val !==$current) {
--$count;
}else{
++$count;
}
if($count==0) {
$current=$nums[$i];
$count=1;
}
}
return $current;
}