Python 算法學習復盤
投票、鏈表與 Top-K 的深度解析

class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        candidate = None  # 當前候選人
        count = 0         # 候選人的「存活票數」

        for num in nums:
            if count == 0:
                # 上一個候選人全數陣亡，換人
                candidate = num
            # 同陣營 +1，不同陣營 -1
            count += (1 if num == candidate else -1)

        # 嚴格多數（> n/2）保證最後存活的就是答案
        return candidate

class Solution:
    def majorityElement(self, nums: list[int]) -> list[int]:
        # 初始化兩個候選人和各自的票數
        c1, c2, cnt1, cnt2 = None, None, 0, 0

        for num in nums:
            if num == c1:
                cnt1 += 1
            elif num == c2:
                cnt2 += 1
            elif cnt1 == 0:
                # c1 陣亡，換 c1
                c1, cnt1 = num, 1
            elif cnt2 == 0:
                # c2 陣亡，換 c2
                c2, cnt2 = num, 1
            else:
                # 兩個陣營都有士兵，遇到第三方就一起抵消
                cnt1 -= 1
                cnt2 -= 1

        # ⚠️ 第二次遍歷驗證（候選人不一定真的超過 n/3）
        result = []
        for c in [c1, c2]:
            if c is not None and nums.count(c) > len(nums) // 3:
                result.append(c)

        return result

class Solution:
    def addTwoNumbers(self, l1, l2):
        # 建立虛擬頭節點：不存資料，只是為了讓後續邏輯統一
        dummy_head = ListNode(0)
        current = dummy_head  # current 指向當前要接新節點的位置
        carry = 0             # 進位值

        while l1 or l2 or carry:
            # 任一鏈表已走完，用 0 補位
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            total = val1 + val2 + carry
            carry = total // 10   # 新的進位
            digit = total % 10    # 當前位的數值

            # 直接接到 current.next，不需要判斷是否為第一個節點
            current.next = ListNode(digit)
            current = current.next

            # 兩個指針各自前進（有值就前進，None 就停著）
            if l1: l1 = l1.next
            if l2: l2 = l2.next

        # dummy_head 本身不是答案，從它的 next 才是真正的結果鏈表
        return dummy_head.next

def majorityElement(nums):
    # 排序後，多數元素超過一半，所以中間位置一定是它
    nums.sort()
    return nums[len(nums) // 2]

# 時間：O(n log n)  空間：O(log n) (Python timsort 的遞迴棧)
# 優點：三行搞定，面試前三分鐘想不到其他解法時的保底

def majorityElement(nums):
    count = {}
    majority_count = len(nums) // 2

    for num in nums:
        count[num] = count.get(num, 0) + 1
        # 邊統計邊檢查，找到就直接回傳
        if count[num] > majority_count:
            return num

    # 題目保證一定有答案，不會走到這裡
    return -1

# 時間：O(n)  空間：O(n)
# 優點：通用，不依賴「絕對多數」的前提

def majorityElement(nums):
    candidate = None
    count = 0

    for num in nums:
        if count == 0:
            # 舊候選人全軍覆沒，換人
            candidate = num
        count += (1 if num == candidate else -1)

    # 「絕對多數」保證：不管如何抵消，最後活下來的就是答案
    return candidate

# 時間：O(n)  空間：O(1)
# 限制：只有嚴格超過 n/2 才保證正確

from collections import Counter

def topKFrequent(nums, k):
    count = Counter(nums)
    # most_common(k) 內部用排序，O(n log n)
    return [num for num, _ in count.most_common(k)]

from collections import Counter
import heapq

def topKFrequent(nums, k):
    count = Counter(nums)
    # 最簡寫法：heapq.nlargest 內部用 min-heap
    # 時間：O(n log k)  — 只維護大小為 k 的堆，而非 n
    return heapq.nlargest(k, count.keys(), key=lambda x: count[x])

# 手動 min-heap 的邏輯（理解原理用）：
# heap = []
# for num, freq in count.items():
#     if len(heap) < k:
#         heapq.heappush(heap, (freq, num))
#     elif freq > heap[0][0]:          # 比堆頂（最小頻率）大才換
#         heapq.heapreplace(heap, (freq, num))
# return [num for _, num in heap]

from collections import Counter

def topKFrequent(nums, k):
    count = Counter(nums)

    # 建立桶：index 代表頻率，最大頻率不超過 len(nums)
    # bucket[i] 裡存所有頻率為 i 的元素
    bucket = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        bucket[freq].append(num)

    # 從高頻率往低頻率收集，收集到 k 個就停
    result = []
    for i in range(len(bucket) - 1, -1, -1):
        result.extend(bucket[i])
        if len(result) >= k:
            return result[:k]  # 截取前 k 個

    return result

# 時間：O(n)  空間：O(n)
# 關鍵洞察：頻率的範圍是固定的 [1, n]，所以可以用桶排序