Single-Pass Optimization (one scan, streaming state) — ஒரு சுற்று மேம்பாடு

ஒரு சுற்று — ஓட்ட ஒருமுறை; ஓட்ட நிலை; கூடுதல் இடம் O(1).

உண்மை உலகில் இது ஏன் முக்கியம்?

உணரி — மீள்வு இல்லை. கட்டண ஓட்டம் — ஒரு சுற்று.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

Dutch flag; Boyer–Moore; ஓட்ட max/min.

Pythonில் முயற்சி செய்வோம்

def boyer_moore_majority(a: list[int]) -> int | None:
    cand, cnt = None, 0
    for x in a:
        if cnt == 0:
            cand, cnt = x, 1
        else:
            cnt += 1 if x == cand else -1
    return cand if a.count(cand) > len(a) // 2 else None


print(boyer_moore_majority([2, 2, 1, 1, 1, 2, 2]))

அடிக்கடி நேரும் தவறுகள்

• random access தேவை — buffer.
• கூட்டு overflow.

முக்கியச் சுருக்கக் குறிப்புகள்

• இரண்டாம் சுற்று sortக்கா? — counting.
• tuple நிலை.