前言

今天接到了一個(gè)面試冻晤，面試官鑫哥聲音很好聽，人也很好绸吸，是我目前見到的所有面試官中最好的一位啦鼻弧。

可能還是知識(shí)面比較窄，第一個(gè)問題就把我給問倒了锦茁。一是太緊張攘轩，二是本身能力可能也沒那么強(qiáng)，所以第一題沒能想出來码俩。面試完后度帮，心里還是墜著一個(gè)石頭似得，就一個(gè)想法稿存，把這個(gè)問題搞明白笨篷，實(shí)現(xiàn)了瞳秽。

于是下午，著手實(shí)現(xiàn)了一下率翅，在此做個(gè)筆記练俐，希望對(duì)后來人能有所幫助。

正文

這道題的內(nèi)容是這樣的：

給一個(gè)數(shù)組安聘，數(shù)組中只有一個(gè)元素出現(xiàn)了僅僅一次痰洒，其他元素都是出現(xiàn)了兩次。請(qǐng)用空間復(fù)雜度為O(1)和時(shí)間復(fù)雜度為O(n)的算法找出這個(gè)數(shù)浴韭。

說實(shí)話，我第一反應(yīng)就是：“尷尬脯宿，這下完蛋了”念颈。肯定不是正規(guī)思路了连霉。然后就想啊想啊榴芳，最后勇于向鑫哥承認(rèn)，這道題我確實(shí)沒有什么好的辦法跺撼。雖然很挫敗窟感，但是最起碼我很誠實(shí)嘛。

def find(array):
    """
    僅適用于數(shù)據(jù)連在一起的情況歉井，如ls = [1,1,2,2,3,3,4,4,5,5,6,6,7,8,8,9,9]
    :param array:
    :return:
    """
    temp = array[0]
    index = 1
    while index<len(array)-1:
        if temp == array[index]:
            temp = array[index+1]
            index += 2
        else:
            return index-1

但是這個(gè)函數(shù)不能處理亂序的數(shù)組柿祈，所以肯定是不行的啦。

思路

下午就搜索了相關(guān)的解題技巧哩至，發(fā)現(xiàn)這是《劍指Offer》的一道題躏嚎。看來我還是準(zhǔn)備的不夠好菩貌，因?yàn)槲覜]看過這本書呢還卢佣。如果之前看到了這本書，估計(jì)今天也不會(huì)這么尷尬了不是箭阶。改天一定要買一本虚茶，好好琢磨琢磨。

對(duì)于這道題仇参，思路是這樣的嘹叫。

比如給定一個(gè)數(shù)組[1,1,2,2,3],讓每一個(gè)元素與其后面的元素進(jìn)行異或運(yùn)算。
最終得到的結(jié)果冈敛，剛好就是那個(gè)僅出現(xiàn)一次的數(shù)的值待笑。

比如對(duì)于這個(gè)數(shù)組：
循環(huán)開始
1^1 = 0  即：十進(jìn)制的0
0^(10)[2] = 10 即：十進(jìn)制的2
10^(10)[2] = 0 即：十進(jìn)制的0
0 ^ （11）[3] = 11 即：十進(jìn)制的3
循環(huán)結(jié)束

(@ο@) 哇～，是不是感覺很神奇呢抓谴？ 反正我是這么覺得暮蹂。數(shù)學(xué)真的是太奇妙了寞缝。

存在一個(gè)數(shù)字

下面我用Python實(shí)現(xiàn)了一下，發(fā)現(xiàn)代碼還是很少的仰泻。

def common(array):
    """
    思路： 第一個(gè)數(shù)和第二個(gè)數(shù)異或運(yùn)算荆陆，得到的結(jié)果再次參與到異或運(yùn)算，最終得到的結(jié)果就是數(shù)組中僅僅出現(xiàn)一次的那個(gè)數(shù)集侯。
    :param array:
    :return:
    """
    position = array[0]
    for index in range(1, len(array)):
        position ^= array[index]
    return position

輸入測(cè)試數(shù)據(jù)：

ls = [1,1,2,2,3,3,4,4,5,5,6,6,7,8,8,9,9]
    position = find(ls)
    print("{} 出現(xiàn)的下標(biāo)位置為：{}".format(ls[position], position))

輸出內(nèi)容：

7 出現(xiàn)的下標(biāo)位置為：12

迄今為止被啼，代碼運(yùn)行的效果還算不錯(cuò)。

存在兩個(gè)數(shù)字

數(shù)組中存在一個(gè)這樣的數(shù)字的情況解決了棠枉，那么如果數(shù)組中有兩個(gè)僅僅出現(xiàn)一次的元素呢浓体？這個(gè)時(shí)候怎么找出來？

答案是拆分?jǐn)?shù)組辈讶。

把大數(shù)組拆分成兩個(gè)小數(shù)組命浴，每個(gè)小數(shù)組中僅包含一個(gè)出現(xiàn)一次的元素。

那么問題的關(guān)鍵來了贱除，到底該怎么分呢生闲？以什么為依據(jù)呢？怎么求得結(jié)果呢月幌？

其實(shí)看完原理后就覺得很簡(jiǎn)單了碍讯。有如下三個(gè)步驟：

• 計(jì)算異或的最終值
• 拆分?jǐn)?shù)組
• 分別計(jì)算得出結(jié)果

關(guān)鍵就在于第二步了。
異或得到的值的二進(jìn)制表示法中肯定有一個(gè)位置（至少有一個(gè)位置）為1扯躺。

比如對(duì)于數(shù)組： 1捉兴，1，2缅帘，2轴术，3
得到的異或值最終為11（二進(jìn)制表示法）。我們按從右至左的順序來搜索第一個(gè)1的位置钦无。然后對(duì)數(shù)組中的其他元素的二進(jìn)制表示的這個(gè)位置進(jìn)行判斷逗栽。如果為1，分到第一個(gè)數(shù)組中失暂，否則分到第二個(gè)數(shù)組彼宠。

因?yàn)橄嗤臄?shù)字，標(biāo)記位一定相同弟塞，不同的數(shù)字凭峡，標(biāo)記位不同，這樣就達(dá)到了我們的要求决记。

為了實(shí)現(xiàn)這個(gè)功能摧冀，我們還需要幾個(gè)小函數(shù)。來方便操作，分別是：

• 求一個(gè)十進(jìn)制數(shù)的二進(jìn)制表示法索昂；

def get_binary_expression(number):
    binarystr = []
    while number!= 0:
        shang = int(number /2 )
        yushu = number - shang*2
        binarystr.append(str(yushu))
        number = shang
    binarystr.reverse()
    return ''.join(binarystr)

• 求一個(gè)二進(jìn)制數(shù)從右至左第一個(gè)不為0的下標(biāo)建车。

def get_noone_position(s):
    # 先反序，為了找到下標(biāo)
    s = [item for item in s]
    s.reverse()
    # print(s)
    s = ''.join(s)
    for index in range(len(s)):
        if int(s[index])==1:
            return index
        else:
            continue

好了萬事俱備椒惨，只剩分組了缤至。

def split(array):
    postfix = common(array)
    flag = get_noone_position(get_binary_expression(postfix))

    print(array)
    subarr1 = []
    subarr2 = []
    # 根據(jù)第position位置上是否為1來分割數(shù)組
    for item in array:
        tempflag = get_noone_position(get_binary_expression(item))
        # print(get_binary_expression(item))
        if tempflag == flag:
            subarr1.append(item)
        else:
            subarr2.append(item)
    print(subarr1)
    print(subarr2)

    num1 = common(subarr1)
    num2 = common(subarr2)
    return num1, num2

下面我們來測(cè)試一下。

輸入數(shù)據(jù)：

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 7, 6, 5, 4, 3, 2, 1]
    num1, num2 = split(array)
    print("Num1: {}, Num2: {}".format(num1, num2))

輸出結(jié)果：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 7, 6, 5, 4, 3, 2, 1]
[1, 3, 5, 7, 9, 7, 5, 3, 1]
[2, 4, 6, 8, 6, 4, 2]
Num1: 9, Num2: 8

發(fā)現(xiàn)大數(shù)組被分成了兩個(gè)子數(shù)組康谆，而且每個(gè)子數(shù)組的的確確是只包含一個(gè)出現(xiàn)了一次的元素领斥。

總結(jié)

實(shí)現(xiàn)了這倆功能，心里的石頭終于落了地沃暗。要不然總覺得少了點(diǎn)什么月洛。

最后，突然發(fā)現(xiàn)孽锥，數(shù)學(xué)真的是好神奇膊存，同時(shí)我也明白了，還有好多東西需要去了解忱叭，去學(xué)習(xí)。這樣在用到的時(shí)候就不會(huì)手忙腳亂今艺， 尷尬面對(duì)了韵丑。