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