IMCSI

0%

php只出现一次的数字问题

发表于 更新于 分类于 Valine：

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:
输入: [2,2,1]
输出: 1

示例 2:
输入: [4,1,2,1,2]
输出: 4

题目解析

根据题目描述，由于加上了时间复杂度必须是 O(n)，并且空间复杂度为 O(1)的条件，因此不能用排序方法，也不能使用 map 数据结构。那么可以使用位操作的特性来解这个题。

由异或运算的性质（相同为0，不同为1），那么出现两次的元素经过异或运算结果为0，那么数组中所有元素异或运算的结果就是剩下的唯一一个值了。

1
2
3
4
5
$arr=array(9,2,2,4,4);
function get_bin($a,$b){
	return $a^$b;
}
echo array_reduce($arr,'get_bin',0);//将数组中所有的值用回调函数进行迭代，获得的结果即是剩下的唯一值

进阶版

将原题的1个数出现一次改为2个不同的数出现一次，其他条件保持不变

首先通过上面的步骤获得2个不同的数的异或结果，由异或的性质得到这两个数至少有一位是不同的，即一个为0，一个为1。

根据异或的性质，任何一个数字异或他自己都等于0，得到这个数字二进制形式中任意一个为1的位都是我们要找的那个位数。

再然后，以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分。

将这一位为 0 的所有元素做异或，得出的数就是只出现一次的数中的一个

将这一位为 1 的所有元素做异或，得出的数就是只出现一次的数中的另一个。

这样就解出题目。忽略寻找不同位的过程，总共遍历数组两次，时间复杂度为 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
$arr=array(899,2,2,4,4,100);
function get_bin($a,$b){
	return $a^$b;
}

echo '两个不同数的异或结果为：'.array_reduce($arr,'get_bin',0)."\r\n";//得到两个不同数的异或结果为3
echo '两个不同数的异或结果的二进制数为：'.decbin(3).PHP_EOL;//将3转换为二进制为11，即得到这两个不同数的二进制位的第1位和第2位都不同
//我们取第一位不同，那么将原数组中所有二进制第1位为1的分为一组，将第1位为0的分为第二组，再将两个数组进行第一步中的迭代就是我们想要获得的两个不同数


function bin_test($num,$wei){//判断二进制某位是否为1 //这里用到按位与的性质 全1为1 否则为0
 $b=1<<($wei-1);//将数字1位移至目标位数//也可将目标数右移至第一位
 if(($b & $num) >0){//按位与 全1为1 否则为0
 	return true;
 }else{
 	return false;
 }
}
foreach ($arr as $value){
 if(bin_test($value,1)){
 	$arr1[]=$value;
 }else{
 	$arr2[]=$value;
 }
}

echo '其中一个数为：'.array_reduce($arr1,'get_bin',0).PHP_EOL;
echo '另一个数为：'.array_reduce($arr2,'get_bin',0).PHP_EOL;