IMCSI

php只出现一次的数字问题

题目描述

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

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

示例 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;

上一篇