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

2019-9-2 星期一 开始吧

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

题目描述

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

题目分析

每题目的要求是在线性的时间内完成，并且不使用额外的空间空间，我们先来看第一版用的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;
    }