当前位置:网站首页>笔试面试题目:求丢失的猪

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

2020-11-08 10:30:34 osc_ccy4urvn

     原文发表于:

 

 

    今天国庆,也是中秋,实在难得。在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仿真

 

版权声明
本文为[osc_ccy4urvn]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4302796/blog/4707993