原文發表于：
今天國慶，也是中秋，實在難得，在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仿真
CSDN認證博客專家
微信公眾號名片
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/207571.html
標籤：其他
下一篇：維圖PDMS切圖軟體