Element większościowy: głosowanie Boyera-Moore’a

Problem elementu większościowego

# The majority element appears MORE than n/2 times
# So it appears more than all other elements COMBINED

examples = [
    [3, 2, 3],          # 3 appears 2/3 times > 1/2
    [2, 2, 1, 1, 1, 2, 2],  # 2 appears 4/7 times > 3.5
    [1],                # trivially 1
    [1, 1, 2, 1],       # 1 appears 3/4 times
]
for e in examples:
    from collections import Counter
    c = Counter(e)
    print(f'Array: {e} → majority: {max(c, key=c.get)} (count {max(c.values())})')

Podejścia przed algorytmem Boyera-Moore’a

from collections import Counter

def majority_sort(nums):
    nums.sort()
    return nums[len(nums) // 2]  # middle is always majority

def majority_hashmap(nums):
    count = Counter(nums)
    return max(count, key=count.get)

def majority_random(nums):
    import random
    n = len(nums)
    while True:
        candidate = random.choice(nums)
        if nums.count(candidate) > n // 2:
            return candidate

nums = [2, 2, 1, 1, 1, 2, 2]
print(majority_sort(nums[:]))   # 2
print(majority_hashmap(nums))   # 2

Algorytm głosowania Boyera-Moore’a

def majority_element(nums):
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num  # new candidate
        if num == candidate:
            count += 1
        else:
            count -= 1
    return candidate

print(majority_element([3, 2, 3]))           # 3
print(majority_element([2, 2, 1, 1, 1, 2, 2]))  # 2
print(majority_element([1]))                 # 1

Intuicja stojąca za algorytmem

def bm_trace(nums):
    candidate = count = 0
    for i, num in enumerate(nums):
        if count == 0:
            candidate = num
        old_count = count
        if num == candidate: count += 1
        else: count -= 1
        print(f'num={num}: candidate={candidate}, count: {old_count}→{count}')
    return candidate

bm_trace([2, 2, 1, 1, 1, 2, 2])
# 2→c=1, 2→c=2, 1→c=1, 1→c=0, 1→new cand=1 c=1, 2→c=0, 2→new cand=2 c=1

Dowód poprawności

# Proof by contradiction visualised:
# Array: [M, M, M, A, B, A, B]  (M is majority, 4/7 times)
# Cancellations: M-A, M-B, M-A, M-B would need 4 non-M elements
# But there are only 4 non-M elements and 4 M's > n/2 = 3.5
# So M can survive: after cancellations, at least 1 M remains uncancelled

def verify_bm(tests):
    for nums in tests:
        result = majority_element(nums)
        brute = max(set(nums), key=nums.count)
        assert result == brute, f'Mismatch: {nums} → BM={result}, Brute={brute}'
    print('All tests passed!')

def majority_element(nums):
    c = cnt = 0
    for n in nums:
        if cnt == 0: c = n
        cnt += 1 if n == c else -1
    return c

verify_bm([[1],[3,2,3],[1,1,2,1],[2,2,1,1,1,2,2]])

Element większościowy II: więcej niż n/3

def majority_element_ii(nums):
    cand1 = cand2 = None
    count1 = count2 = 0
    for num in nums:
        if num == cand1: count1 += 1
        elif num == cand2: count2 += 1
        elif count1 == 0: cand1, count1 = num, 1
        elif count2 == 0: cand2, count2 = num, 1
        else:
            count1 -= 1
            count2 -= 1
    # Verify: candidates must exceed n/3
    n = len(nums)
    return [c for c in [cand1, cand2]
            if c is not None and nums.count(c) > n // 3]

print(majority_element_ii([3, 2, 3]))      # [3]
print(majority_element_ii([1, 2]))          # [1, 2]
print(majority_element_ii([1, 1, 1, 3, 3, 2, 2, 2]))  # [1, 2]

Uogólniony algorytm Boyera-Moore’a: większość n/k

def majority_nk(nums, k):
    '''Find all elements appearing more than n/k times.'''
    counts = {}  # candidate -> count
    for num in nums:
        counts[num] = counts.get(num, 0) + 1
        if len(counts) >= k:
            # Remove all candidates by decrementing
            new_counts = {c: cnt-1 for c, cnt in counts.items() if cnt > 1}
            counts = new_counts
    # Verify
    threshold = len(nums) // k
    return [c for c in counts if nums.count(c) > threshold]

print(majority_nk([1,2,3,1,2,1,2,1], 3))  # [1, 2] (both > 8/3 ≈ 2.67)
print(majority_nk([1,1,1,2,2,3,3,3], 4))  # [1, 3] (both > 8/4 = 2)

Element większościowy metodą dziel i zwyciężaj

def majority_dc(nums, lo=None, hi=None):
    if lo is None: lo, hi = 0, len(nums) - 1
    if lo == hi: return nums[lo]
    mid = (lo + hi) // 2
    left_maj  = majority_dc(nums, lo, mid)
    right_maj = majority_dc(nums, mid + 1, hi)
    if left_maj == right_maj:
        return left_maj
    # Count both candidates across the sub-range
    left_count  = sum(1 for i in range(lo, hi+1) if nums[i] == left_maj)
    right_count = sum(1 for i in range(lo, hi+1) if nums[i] == right_maj)
    return left_maj if left_count > right_count else right_maj

print(majority_dc([3, 2, 3]))            # 3
print(majority_dc([2, 2, 1, 1, 1, 2, 2]))  # 2

Boyer-Moore a inne metody

import time, random

nums = [random.randint(1, 100) for _ in range(500000)]
# Make element 42 the majority
nums = [42] * 300000 + nums[:200000]
random.shuffle(nums)

start = time.time()
from collections import Counter
hm = Counter(nums).most_common(1)[0][0]
print(f'HashMap: {hm} in {time.time()-start:.4f}s')

def bm(nums):
    c = cnt = 0
    for n in nums: 
        if cnt == 0: c = n
        cnt += 1 if n == c else -1
    return c

start = time.time()
result = bm(nums)
print(f'Boyer-Moore: {result} in {time.time()-start:.4f}s')
print(f'Both correct: {hm == result}')

Gdy nie ma gwarancji istnienia elementu większościowego

def majority_element_safe(nums):
    '''Returns majority element or None if it doesn't exist.'''
    # Phase 1: find candidate
    candidate = count = 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    # Phase 2: verify
    if nums.count(candidate) > len(nums) // 2:
        return candidate
    return None

print(majority_element_safe([3, 2, 3]))   # 3 (majority exists)
print(majority_element_safe([1, 2, 3]))   # None (no majority)
print(majority_element_safe([1, 2, 1, 2]))  # None (tie, neither > n/2)

Przebieg rozwiązania podczas rozmowy kwalifikacyjnej

# Clean 5-line Boyer-Moore for interviews
def majority_element(nums):
    c, cnt = nums[0], 1
    for n in nums[1:]:
        cnt += (1 if n == c else -1)
        if cnt == 0: c, cnt = n, 1
    return c

# Verification (if majority not guaranteed)
def majority_with_check(nums):
    c = majority_element(nums)
    return c if nums.count(c) > len(nums) // 2 else -1

print(majority_element([3, 2, 3]))  # 3
print(majority_element([2, 2, 1, 1, 1, 2, 2]))  # 2
print('Time: O(n), Space: O(1)')

Szybki test

Podsumowanie lekcji