9

一道面试题的思考 - Limboy's HQ

 3 years ago
source link: https://limboy.me/2011/06/03/php-xor-find-num/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

前几天下班途中跟同事聊到了一道面试题，大意是，给你1-1000个连续自然数，然后从中随机去掉两个，再打乱顺序，要求只遍历一次，求出被去掉的两个数。

这题其实挺为面试者的，因为要求1分钟内说出解法，且不能使用计算机、纸和笔。如果之前没有遇到过类似的题目，加上面试时的紧张心情，很难能在那么短的时间里想到解决方案，至少我做不到。

好在我有时间，上网看了一下，比较常见的有两种方法

求方程组的解

遍历被打乱的数组时，计算value的累加值和value平方的累加值。结合未打乱之前的数组，这样就能得出x+y = m与xx+yy = n两个方程，解这组方程即可算出被去掉的两个数。这种方法比较容易理解，实现起来也比较简单

这个就麻烦点了。先来说说异或的定义：两个二进制位不同的取1。再来说说异或的两个特性：顺序无关 / 对一个数异或两次等于没有异或。顺序无关就是说异或的元素可以随意交换顺序，而不会影响结果。异或两次可以理解为+x和-x。

计算出x^y的值

首先，这两个数组(打乱前和打乱后)各自异或，也就是1^2^…^1000，得到两个异或值。再对这两个异或值进行一次异或，这样就得到了x^y的指(重复部分互相抵消了)。

// 其实就是把数组的所有元素进行异或，重复部分互相抵消
result = 1^2^...^1000^1^2...^1000;
result = 1^1^2^2...^x...^y...^1000^1000;
result = x^y;

获取计算出的异或值的1所在的位置，并继续异或

因为x和y是两个不同的整数，所以这两个数的异或结果，转化为二进制的话，一定在某位是1，假设在第3位。也就是说如果把原始数组按第3位是否为0进行划分，就可以分成两个数组，每个数组各包含一个被抽取的数。如果打乱后的数组也按这个规则划分为两个数组，这样就得到了4个数组，其中两组是第3位为0，另外两组是第3位为1。把第3位为0的两个数组所有元素进行异或就能得到被抽取的一个数，同理也就能获得另外一个被抽取的数，于是问题解决。

PHP的实现

<?php 
// 起始长度
$length = 10;

$arr = $arr_copy = range(1, $length);
// 将要被移除的两个数
$num1 = $num2 = 0;
// 两个数组异或再互相异或的结果
$num1_num2_xor = 0;
// 存放被pos分割的数字
$arr_0 = $arr_1 = $arr_copy_0 = $arr_copy_1 = array();

// 获取一个数字转化为二进制后1所在的位置
function get_pos($num)
{
	for($i=0 ;$i<10; $i++)
	{
		$b = pow(2, $i);
		$rs = $num&$b;
		if($rs % 2 == 0 && $rs != 0)
		{
			return $i;
		}
	}
	return 0;
}

// 进行异或计算
function do_xor($x, $y)
{
	return $x^$y;
}

function init()
{
	global $arr, $arr_copy, $num1, $num2, $num1_num2_xor, $length;

	$rand_index_1 = mt_rand(1, $length/2);
	$rand_index_2 = mt_rand($length/2+1, $length-1);

	// 获取两个随机数，然后去掉从数组中去掉它们
	$num1 = $arr[$rand_index_1];
	$num2 = $arr[$rand_index_2];

	unset($arr[$rand_index_1]);
	unset($arr[$rand_index_2]);

	cacl_num1_num2_xor();
	divide_by_pos(get_pos($num1_num2_xor));
	get_num();

}

// 获取两个数组各自异或再互相异或的结果
function cacl_num1_num2_xor()
{
	global $arr, $arr_copy, $num1_num2_xor;
	$arr_xor = array_reduce($arr, 'do_xor');
	$arr_copy_xor = array_reduce($arr_copy, 'do_xor');

	$num1_num2_xor = $arr_xor ^ $arr_copy_xor;
}

// 根据pos将两个数组再各自细分成两个数组
// 其中$arr_copy_0和$arr_copy_1各自包含了一个被抽取的数
function divide_by_pos($pos)
{
	global $arr, $arr_copy, $arr_0, $arr_1, $arr_copy_0, $arr_copy_1;
	$b = pow(2, $pos);

	foreach($arr as $val)
	{
		$rs = $val&$b;
		if($rs == 0)
		{
			$arr_0[] = $val;
		}
		else
		{
			$arr_1[] = $val;
		}
	}

	foreach($arr_copy as $val)
	{
		$rs = $val&$b;
		if($rs == 0)
		{
			$arr_copy_0[] = $val;
		}
		else
		{
			$arr_copy_1[] = $val;
		}
	}
}

// 对这4个数组进行对应的异或操作，就出结果了
function get_num()
{
	global $arr_0, $arr_1, $arr_copy_0, $arr_copy_1, $num1, $num2;
	$arr_0_xor = array_reduce($arr_0, 'do_xor');
	$arr_copy_0_xor = array_reduce($arr_copy_0, 'do_xor');
	$cacl_num1 = $arr_0_xor^$arr_copy_0_xor;

	$arr_1_xor = array_reduce($arr_1, 'do_xor');
	$arr_copy_1_xor = array_reduce($arr_copy_1, 'do_xor');
	$cacl_num2 = $arr_1_xor^$arr_copy_1_xor;

	echo $cacl_num1.' / '.$cacl_num2. PHP_EOL;
	echo $num1.' / '.$num2;
}

init();

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK