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

2 0 1 9 - 3 - 1 1   星 期 一       开 始 吧

题目描述

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

题目示例

例 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];
    }

这 代 码 你 们 一 看 就 明 白 了 , 主 要 是 分 析 一 下 他 的 时 间 复 杂 度 . 很 明 显 我 们 搜 索 了 整 个 数 组 , 并 且 查 找 值 是 否 存 在 定 义 的 数 组 中 , 这 个 查 找 的 过 程 是 在 f o r 循 环 中 进 行 的 , 所 以 他 的 时 间 复 杂 度 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 ) .