ROSALIND｜Majority Element (MAJ)

發表於 更新於

給定長度為 n 的數列，求其中出現頻率大於五成的數字。

Given: A positive integer $k \leq 20$, a positive integer $n \leq 10^4$, and $k$ arrays of size $n$ containing positive integers not exceeding $10^5$.

Return: For each array, output an element of this array occurring strictly more than $n / 2$ times if such element exists, and “-1“ otherwise.

(https://rosalind.info/problems/maj/)

計數法

遍歷整個數列，統計各數字的出現頻率，最後判斷出現頻率大於五成的數字。因為要同時記錄數字和出現頻率，所以時間與空間複雜度均為線性。

1
2
3
4
5
6
7
8
9
10
11
def maj_freq(l):
    freqs = {}
    for e in l:
        if e in freqs:
            freqs[e] = freqs[e] + 1
        else:
            freqs[e] = 1
    for e, freq in freqs.items():
        if freq > len(l) // 2:
            return e
    return -1

Boyer–Moore majority vote algorithm

這方法的時間複雜度同為線性，但空間複雜度為常數，不隨數列長度增加。假設數列裡存在出現頻率大於五成的數字，從數列移除一對相異數字並不會影響這個事實。

基於這項觀察，Boyer-Moore 方法分為兩階段，首先是讓相異數字互相抵銷，最後判斷留下來的數字的出現頻率是否大於五成。舉例來說，數列 [1, 2, 1, 2, 1] 的主要數字是 1。移除前兩個數字變成 [1, 2, 1] 之後，數列的主要數字還是 1。

這個過程是由一個計數器來實現，從數列第一個數字開始計算，碰到相同數字就加一，碰到相異數字則減一。一旦計數器歸零，則更新比對的數字，直到遍歷整個數列。


（如果數列存在出現頻率大於五成的數字，遍歷整個數列後計數器應為正值。圖/維基百科）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maj_bm(l):
    candidate = None
    count = 0
    for e in l:
        if count == 0:
            candidate = e
            count = 1
        if e == candidate:
            count = count + 1
        else:
            count = count - 1
    if l.count(candidate) > len(l) // 2:
        return candidate
    return -1

遞迴法

如果兩數列的眾數相同，該數字也會是兩數列合併後的眾數，例如 [1, 2, 1]、[1, 3] 的眾數都是 1，合併數列 [1, 2, 1, 1, 3] 的眾數也是 1。基於這項觀察，可將數列拆分成較小的片段，分別計算各數列出現頻率大於五成的數字，再合併結果得出原數列的眾數。

在這題的情境中，最小可以拆成長度為一的數列，其中數字的出現頻率自然大於五成。若兩數列的眾數相同，則可直接以該數字為合併數列的代表。如果兩數列的眾數不同，則要判斷兩個數字在合併後的出現頻率是否大於五成。

舉例來說 [1, 2, 1, 1] 的眾數是 1，[1, 2, 2] 的眾數是 2，合併數列 [1, 2, 1, 1, 1, 2, 2] 的眾數是 1 且其出現頻率也大於五成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def maj_rc(l):
    if not l:
        return -1
    
    if len(l) == 1:
        return l[0]

    mid = len(l) // 2
    left = maj_rc(l[:mid])
    right = maj_rc(l[mid:])

    if left == right:
        return left

    else:
        if l.count(left) > len(l) // 2:
            return left
        elif l.count(right) > len(l) // 2:
            return right
        else:
            return -1

題目要求以 -1 表示數列不存在出現頻率大於五成的數字。照理在判斷式裡面要特別處理，但題目已經限定正整數數列，就把它當一般數字了，看起來是不影響結果。