一, 题目
给定一个非空整数数组, 除了某个元素只出现一次以外, 其余每个元素均出现两次. 找出那个只出现了一次的元素.
说明: 你的算法应该具有线性时间复杂度. 你可以不使用额外空间来实现吗?
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 为该元素出现的次数.
- function singleNumber($nums) {
- $valueCnt = array_count_values($nums);
- return array_search(1, $valueCnt) !== false ? array_search(1, $valueCnt) : false;
- }
解法 2: 哈希表
设置一个哈希数组, 遍历给定数组的元素, 如果该元素不在哈希表里, 就将该元素放入哈希表中, 反之, 则将该元素从哈希表中移除. 最后哈希表剩下的元素肯定只有一个, 则为所求解. 但这个不满足条件中提到的 "不使用额外空间".
时间复杂度: O(n), 空间复杂度: O(n)
- 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)
- 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(十进制).
来源: https://www.cnblogs.com/sunshineliulu/p/12459669.html