剑指 Offer 40：撲克牌順子判斷 - 排序與間隙填充法

問題描述

從撲克牌中隨機抽 5 張牌，判斷是否為順子。規則：2-10 為本身數字，A=1，J=11，Q=12，K=13，大小王可視為任意數字（用 0 表示）。

核心思路：排序 + 統計 0 + 計算間隙

1. 排序：將 5 張牌排序
2. 統計 0 的個數：大小王數量，可用於填補間隙
3. 計算非 0 牌之間的間隙總數：相鄰非 0 牌差值 - 1
4. 判斷邏輯：若間隙總數 ≤ 0 的個數，且無重複非 0 牌，則為順子

關鍵細節

• 重複非 0 牌直接返回 false（對子不可能是順子）
• 0 可填補任意間隙，如 {0,1,3,4,5} 中 1 和 3 間隙為 1，剛好有一個 0 填補
• 全為 0 視為順子

C++ 完整實現

bool IsContinuous(int* cards, int length) {
    if (cards == NULL || length <= 0) return false;
    
    sort(cards, cards + length);
    
    int zeroCount = 0;
    for (int i = 0; i < length; ++i)
        if (cards[i] == 0) zeroCount++;
    
    int gapCount = 0;
    int prev = cards[zeroCount]; // 第一個非 0 牌
    for (int i = zeroCount + 1; i < length; ++i) {
        int cur = cards[i];
        if (cur == prev) return false; // 重複牌
        gapCount += cur - prev - 1;    // 累加間隙
        prev = cur;
    }
    
    return gapCount <= zeroCount;
}

複雜度分析

• 時間複雜度：O(1)（固定 5 張牌，排序常數時間）
• 空間複雜度：O(1)

測試用例

• {0,1,3,4,5} → true (0 填 2)
• {0,0,1,2,5} → true (兩 0 填 3,4)
• {1,2,3,4,5} → true
• {1,2,3,4,4} → false (重複)
• {10,11,12,13,0} → true (0 填 9 或 14 視為順子)