【題目描述】
Given an array contains?N?numbers of 0 ..N, find which number doesn't exist in the array.
給出一個(gè)包含 0 ..N中N個(gè)數(shù)的序列盲再，找出0 ..N中沒有出現(xiàn)在序列中的那個(gè)數(shù)绸栅。
【題目鏈接】
www.lintcode.com/en/problem/find-the-missing-number/
【題目解析】
最直觀的思路是對(duì)數(shù)據(jù)進(jìn)行排序，然后依次掃描丈秩，便能找出漏掉的數(shù)字希停，但是基于比較的排序算法的時(shí)間復(fù)雜度至少是nlog(n)烁巫，不滿足題目要求。
一種可行的具有線性時(shí)間復(fù)雜度的算法是求和宠能。對(duì)0到n求和亚隙，然后對(duì)給出的數(shù)組求和，二者之差即為漏掉的數(shù)字违崇。但是這種方法不適用于0是漏掉的數(shù)字的情況阿弃，因?yàn)榇藭r(shí)兩個(gè)和是相同的诊霹。（或者也能由此得出漏掉的數(shù)字是0）
從CPU指令所耗費(fèi)的時(shí)鐘周期來看，比加法更高效率的運(yùn)算是異或(XOR)運(yùn)算渣淳。本題的標(biāo)簽里有位運(yùn)算脾还，暗示本題可以用位運(yùn)算的方法解決。
異或運(yùn)算的一個(gè)重要性質(zhì)是入愧，相同的數(shù)異或得0鄙漏，不同的數(shù)異或不為0，且此性質(zhì)可以推廣到多個(gè)數(shù)異或的情形棺蛛。本題的解法如下怔蚌，首先將0到n這些數(shù)進(jìn)行異或運(yùn)算，然后對(duì)輸入的數(shù)組進(jìn)行異或運(yùn)算旁赊，最后將兩個(gè)結(jié)果進(jìn)行異或運(yùn)算桦踊，結(jié)果便是漏掉的數(shù)字，因?yàn)槠渌麛?shù)字在兩個(gè)數(shù)組中都是成對(duì)出現(xiàn)的终畅，異或運(yùn)算會(huì)得到0籍胯。
【參考答案】
