亲宝软件园·资讯

展开

LeetCode#136 | Single Number 只出现一次的数字

鹿呦呦 人气:0
#### 一、题目 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明:你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗? > Given an array of integers, every element appears twice except for one. Find that single one. Note: > > Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? > > Example 1: > Input: [2,2,1] > Output: 1 > > Example 1: > Input: [4,1,2,1,2] > Output: 4 #### 二、题解 - 解法1:PHP自带函数 array_count_values() PHP 的 array_count_values() 函数可以用于统计数组中所有值出现的次数。返回的结果也是一个数组,key 为数组中的元素,value 为该元素出现的次数。 ```php function singleNumber($nums) { $valueCnt = array_count_values($nums); return array_search(1, $valueCnt) !== false ? array_search(1, $valueCnt) : false; } ``` - 解法2:哈希表 设置一个哈希数组,遍历给定数组的元素,如果该元素不在哈希表里,就将该元素放入哈希表中,反之,则将该元素从哈希表中移除。最后哈希表剩下的元素肯定只有一个,则为所求解。但这个不满足条件中提到的“不使用额外空间”。 **时间复杂度:O(n),空间复杂度:O(n)** ```php function singleNumber($nums) { $arr = []; foreach ($nums as $num) { if (!in_array($num, $arr)) { $arr[] = $num; } else { array_splice($arr, array_search($num, $arr), 1); } } return $arr[0]; } ``` - 解法3:异或 这个是看了题解才知道还有这么简单的方法!很久没用“异或”这个位运算符了。 ``` 对 0 和二进制位做 XOR 运算,得到的仍然是这个二进制位; 对相同的二进制位做 XOR 运算,返回的结果是 0; ``` **时间复杂度:O(1),空间复杂度:O(n)** ```php function singleNumber($nums) { $ans = 0; foreach ($nums as $num) { $ans = $ans ^ $num; } return $ans; } ``` 运算过程如下: ans = 0,num = 3:0 ^ 3 = 0 ^ 11(二进制) = 11(二进制) = 3(十进制); ans = 3,num = 1:3 ^ 1 = 11(二进制) ^ 1 = 10(二进制) = 2(十进制); ans = 2,num = 1:2 ^ 1 = 10(二进制) ^ 1 = 11(二进制) = 3(十进制); ans = 3,num = 2:3 ^ 2 = 11 ^ 10(二进制) = 01(二进制) = 1(十进制); ans = 1,num = 3:1 ^ 3 = 1 ^ 11(二进制) = 10(二进制) = 2(十进制)。

加载全部内容

相关教程
猜你喜欢
用户评论