首頁猿問面試中遇到的一道算法題

面試中遇到的一道算法題

面試

繁華開滿天機(jī) 2018-08-01 17:22:41

有一堆數(shù)，其中有兩個數(shù)出現(xiàn)了一次，其他的數(shù)都出現(xiàn)了兩次。怎樣將這兩個只出現(xiàn)一次的數(shù)找出來？排除打表，統(tǒng)計外有什么更為高效的方法。

查看完整描述

3 回答

慕姐4208626

TA貢獻(xiàn)1852條經(jīng)驗獲得超7個贊

1先把所有數(shù)字做異或操作得到數(shù)字 S
2 從高到低位檢查 S 的 bit 找到第一個 1
3 檢查所有數(shù)字根據(jù) 這個bit位是1 還是 0 把原來的數(shù)組劃分為兩個
4 對每個數(shù)組，把數(shù)組內(nèi)的數(shù)字做異或操作。分別得到數(shù)字 A ,B
5 數(shù)字 A ,B 即為所求

時間復(fù)雜度 O(n)
空間復(fù)雜度 O(1)

反對回復(fù) 2018-08-04