資訊專欄INFORMATION COLUMN
摘要：如何使用異或運算找到數組中缺失的數今天給大家分享一篇關于使用異或運算找到數組中缺失的數的問題。第二種解法通過對所有整數的進行，然后將得到的結果對剩余數組中所有項的進行異或。
如何使用異或（XOR）運算找到數組中缺失的數？
今天給大家分享一篇關于使用XOR（異或）運算找到數組中缺失的數的問題。
在一次Javascript面試中，有這么一個問題：
假設有一個由0到99（包含99）的整數組成的長度為100的數組。從數組中隨機移除一個元素，得到了一個長度為99的數組，那么請問如何找到所取出的數字是幾？（假設數組未排序）。
大多數面試者都是按照如下方法解答的：
首先對數組進行排序，然后遍歷一遍數組，檢查數組中相鄰兩項的的差，如果差大于1，則找到缺失的數字。
這是一種有效的算法。但是由于涉及排序，會消耗額外的計算成本。所以問題在于如何在只遍歷一遍數組的情況下找到缺失的數。
第一種解法計算剩余99個整數的和，以及0-99所有整數的總和，就可以用0-99之間所有整數的總和減去數組中剩余數的和來得到缺少的數。
第二種解法通過對所有整數[0..99]的進行XOR，然后將得到的結果對剩余數組中所有項的進行異或。
更多詳細內容可以查看原文。今天的文章就分享到這啦。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/100009.html