Leetcode之PHP版题目解析(136. Single Number)

2019-3-11 星期一   开始吧

题目描述

给一个不为空的数组,除了一个元素外,每一个元素都会出现两次,找出那个出现一次的数.

题目示例

例1输入[2,2,1],那么返回的就是出现一次的1,例2输入的是[4,1,2,1,2],那么输出的就是出现一次的4.

题目思路

我的思路(好吧我第一次使用的是暴力破解法,这是一种超级常规的思想,看看就好,他的运行效率会很低,不推荐这种,既然我们刷题了,当然要用更优的解法做题)

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums) {
        $data=[];
       foreach($nums  as $num) {
           if(!in_array($num,$data)) {
               array_push($data,$num);
           }else{
               $index=array_search($num,$data);
               array_splice($data,$index,1);
           }
       }
        return $data[0];
    }

这代码你们一看就明白了,主要是分析一下他的时间复杂度.很明显我们搜索了整个数组,并且查找值是否存在定义的数组中,这个查找的过程是在for循环中进行的,所以他的时间复杂度O(n*n),空间复杂度就是O(n).运行结果惨不忍睹.

我们可以通过运算符异或(^)来进行比较,当^左边等于右边时,结果为默认值0,当^的左边不等于右边时,结果返回默认值1.所以我们可以将所有的位异或找出唯一的值.

实现代码

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums) {
        $res=0;
        for($i=0;$i<count($nums);$i++) {
            $res ^=$nums[$i];
        }
        return $res;
    }

时间复杂度,我们只是循环了数组,所以时间复杂度是O(n),空间复杂度常量O(1).