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

集合+統(tǒng)計

解題思路

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

Python 實現(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ù)組，并對出現(xiàn)的數(shù)進行計數(shù)b，當出現(xiàn)不同的數(shù)時，判斷上一個數(shù)出現(xiàn)次數(shù)是奇數(shù)還是偶數(shù)。

Python 實現(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]

改進版本：

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

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)計

解題思路

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

Python 實現(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

位運算

解題思路

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

Python 實現(xiàn)

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