有一個(gè)數(shù)組，其中的數(shù)都是以偶數(shù)次的形式出現(xiàn)，只有一個(gè)數(shù)出現(xiàn)的次數(shù)為奇數(shù)次，要求找出這個(gè)出現(xiàn)次數(shù)為奇數(shù)次的數(shù)。

集合+統(tǒng)計(jì)

解題思路

最簡(jiǎn)單能想到的，效率不高。利用集合的特性，通過(guò) Python 的 set() 函數(shù)篩選出數(shù)組中有哪些數(shù)，然后遍歷集合，使用 List 的 count 方法統(tǒng)計(jì)集合中每個(gè)元素在數(shù)組中出現(xiàn)的次數(shù)，如果是奇數(shù)次則直接返回該數(shù)。

Python 實(shí)現(xiàn)

def find_odd_times_num(arr):
    num = set(arr)    for i in num:        if arr.count(i) % 2 != 0:            return i

排序+遍歷

解題思路

將數(shù)組從小到大排序，然后遍歷數(shù)組，并對(duì)出現(xiàn)的數(shù)進(jìn)行計(jì)數(shù)b，當(dāng)出現(xiàn)不同的數(shù)時(shí)，判斷上一個(gè)數(shù)出現(xiàn)次數(shù)是奇數(shù)還是偶數(shù)。

Python 實(shí)現(xiàn)

def find_odd_times_num(arr):
    arr.sort()
    cnt = 1
    for i in range(1, len(arr)):        if arr[i] != arr[i - 1]:            if cnt % 2 != 0:                return arr[i-1]            else:
                cnt = 1
        else:
            cnt += 1
    if cnt % 2 != 0:        return arr[i]

改進(jìn)版本：

借用計(jì)數(shù)排序的思想，先找到數(shù)組中最大的元素，然后開辟一個(gè)新數(shù)組，原數(shù)組中每個(gè)元素的值即為新數(shù)組的下標(biāo)，遍歷原數(shù)組記錄每個(gè)元素出現(xiàn)的次數(shù)，最后遍歷新數(shù)組，找到奇數(shù)，返回其下標(biāo)。

def find_odd_times_num(arr):
    m = max(arr)
    cnt = [0] * m    for i in arr:
        cnt[i-1] += 1
    for j in range(m):        if cnt[j] % 2 != 0:            return j+1

Map + 統(tǒng)計(jì)

解題思路

遍歷數(shù)組記錄出現(xiàn)次數(shù)先計(jì)數(shù)，并存儲(chǔ)到 Map 中，再遍歷 Map，找出 Map 中 value 為奇數(shù)的 key。

Python 實(shí)現(xiàn)

def find_odd_times_num(arr):
    dict = {}    for i in arr:        if i in dict:
            dict[i] += 1
        else:
            dict[i] = 1
    for k, v in dict.items():        if v % 2 != 0:            return k

位運(yùn)算

解題思路

巧妙地采用異或的特點(diǎn)進(jìn)行處理，即整數(shù) n 與 0 的異或結(jié)果為 n，整數(shù) n 與 n 的異或結(jié)果為 0，異或運(yùn)算滿足交換律和結(jié)合律。即，所有出現(xiàn)偶數(shù)次的python基礎(chǔ)教程數(shù)異或的結(jié)果為 0，而對(duì)于出現(xiàn)次數(shù)為奇數(shù)次n的數(shù)，其出現(xiàn)的前 n-1 次異或的結(jié)果為 0，而 0 與其最后1次出現(xiàn)進(jìn)行異或，得到該數(shù)本身。因此，可以很方便找出出現(xiàn)次數(shù)為奇數(shù)次的數(shù)。

Python 實(shí)現(xiàn)

def find_odd_times_num(arr):
    res = 0
    for i in arr:
        res ^= i    return res