137.md

✏️Leetcode基础刷题之(137. Single Number II)

2019-09-02 吴亲库里 库里的深夜食堂

---

✏️描述

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

---

✏️题目实例

​

✏️题目分析

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

---

联系

​