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


2019-3-25 星期一  开始吧

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

d0cc237f3e4a059c54b24c760a5f92aa.png

题目描述

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

题目分析

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

点赞 取消点赞 收藏 取消收藏

<< 上一篇: Leetcode PHP题解--D14 561. Array Partition I

>> 下一篇: Leetcode PHP题解--D15 509. Fibonacci Number