算法题那点事儿

连续1到n的数字缺少x,乱序存在一个数组中,找出这个x是多少

1
2
3
4
5
6
7
8
9
10
11
//异或有个很巧妙的地方:同一变量和该变量与另一变量的异或值的异或等于这个变量自身,最后计算下来时间复杂度为O(n),空间复杂度为O(1)
$a = [1,2,3,4,8,6,7,9,10,11,12];
$x = 0;
$y = 0;
for($i=1; $i<=12; $i++) {
$y^=$i;
}
foreach($a as $i) {
$x^=$i;
}
echo $x^$y;//5