Leetcode基础刷题之PHP解析(137. Single Number II)


2019-9-2 星期一 开始吧

上一题链接Leetcode基础刷题之PHP解析(135. Candy)

90006381c31862195f4ebc8ed4c53e2f.png


题目描述

给定一个非空的整形数组,除了一个数,其他数都出现三次,找出那个数。


题目分析

每题目的要求是在线性的时间内完成,并且不使用额外的空间空间,我们先来看第一版用的php中的函数解。先统计出每个值出现的次数,然后再找出值为1次的那个键即可,简单粗暴
代码实现

/**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums) {     
        return array_search(1,array_count_values($nums));
    }

 看到大神是用位运算来求解的,用三个变量来表示第i位置上出现1,2,3次的掩码变量。可以感受一下代码。

/**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums) {
        $ones=0;$twos=0;$threes=0;
        for($i=0;$i<count($nums);$i++){
            $twos |=$ones & $nums[$i];
            $ones ^=$nums[$i];
            $threes =$ones & $twos;
            
            $ones &= ~$threes;
            $twos &= ~$threes;
        }
        return $ones;
    }

Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode基础刷题之PHP解析(135. Candy)

>> 下一篇: Laravel 6.0 版本正式发布了!