Leetcode之PHP版题目解析（169. Majority Element)

2019-3-25 星期一  开始吧

上一题链接 Leetcode之PHP版题目解析（168. Excel Sheet Column Title)

题目描述

给你一个整数数组，找出多数元素，多数元素表示出现的次数超过数组的二分之一。

题目分析

题目已经说明，你可以假设这不是一个空数组，并且一定存在多数元素，我们可以这样，循环整个数组，记录下每一个数组出现的次数，然后进行判断元素出现的次数大于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;
         
    }