笔试面试题目：求丢失的猪

     原文发表于：

 

 

    今天国庆，也是中秋，实在难得。在21世纪的100年内，仅有4年是这样的。今天在家里，陪家人，做饭吃，干家务活，看点闲书，顺便写点东西，待会出去逛逛，然后回来跑跑步。

 

     校园秋招陆续开始了，祝在校同学拿到心仪的offer，也祝社招的同学跳槽顺利。

      今天，我们来看下A公司的一个面试题：

      有n只猪，用车拉到菜市场去卖，这群猪的身上分别贴了1~n的编号，突然，有一只猪从车上跳下溜走了，求溜走的猪的编号。

 

    

      这猪还是挺可怜的，溜走了，也要追查编号。下面，我们来看看算法。

 

算法1：作差法

       思路：

       Step1: 计算出1~n的和a.

       Step2: 求剩余猪的编号之和b.

       Step3: a-b即为溜走猪的编号。

 

       这种算法的缺点是：求1~n的和，可能会溢出。

 

算法2：标记法

     思路：开辟一个数组m，用m[i]=0或1来记录i是否存在，针对丢失的猪j, 必有m[j]=0.

     这种算法的缺点是：空间复杂度为O(n)

 

算法3：排序法

      思路：对剩余的猪进行排序，在溜走的猪j的编号处，必然出现断裂，从而知道j的具体值。

     这种算法的缺点是：以快排为例，时间复杂度和空间复杂度都无法达到最优。

 

算法4：异或法(最佳算法)

       思路：

       Step1: 计算出1~n的异或值a.

       Step2: 求剩余猪的编号异或值b.

       Step3: 求a和b的异或值，即为溜走的猪的编号j.

 

       原理如下:

       假设n=5, 丢失的猪的编号是3, 那么剩余的猪的编号是2, 4, 1, 5，下面我们来计算：

       j = 1^2^3^4^5^2^4^1^5

      显然，根据异或的交换律性质，可以对上述运算进行简化，如下：

       j = 1^1^2^2^4^4^5^5^3 = 3

      

      这就求出了溜走的猪的编号。此时，时间复杂度是O(n), 空间复杂度是O(1), 这是最佳算法。至于程序，很简单，故不再赘述。

 

 

      在之前的文章中，我们其实可以看到，异或是一种特殊的“加减法”，所以，算法1和算法4是有异曲同工之妙的。关于二进制的异或，可以参考：

      计算机加法的电路原理及proteus仿真