当前位置:网站首页>笔试面试题目:求丢失的猪
笔试面试题目:求丢失的猪
2020-11-08 10:30:00 【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是有异曲同工之妙的。关于二进制的异或,可以参考:
版权声明
本文为[osc_ccy4urvn]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4302796/blog/4707993
边栏推荐
猜你喜欢
随机推荐
Adobe Prelude / PL 2020 software installation package (with installation tutorial)
虚拟机中安装 macOS 11 big sur
Ulab 1.0.0 release
Oschina plays on Sunday - before that, I always thought I was a
2020-11-05
How did Julia become popular?
阅读心得:FGAGT: Flow-Guided Adaptive Graph Tracking
进程、线程和协程的区别
If you don't understand the gap with others, you will never become an architect! What's the difference between a monthly salary of 15K and a monthly salary of 65K?
游戏优化性能杂谈(十一) - 知乎
Deeplight Technology Bluetooth protocol SRRC certification services
2 days, using 4 hours after work to develop a test tool
Px4 adds new applications
An error occurred while starting the kernel was successfully resolved
TCP协议如何确保可靠传输
学习小结(关于深度学习、视觉和学习体会)
Shiyou's numerical analysis assignment
PDMS cutting software
Basic concepts of computer network (5) basic principles of local area network
盘点那些你没想到的云计算应用场景(上)