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

Leetcode · curry · 于 24天前 发布 · 27 次阅读

题目描述

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

题目示例

例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(nn),空间复杂度就是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;
}

本文由 curry 创作,采用 知识共享署名 3.0 中国大陆许可协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

共收到 0 条回复 php 算法
没有找到数据。
添加回复 (需要登录)
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册
吴亲库里的深夜食堂