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