846. 一手顺子

[JalanJiang]

• 原题链接：846. 一手顺子
• 题解链接：http://jalan.space/leetcode-notebook/#/algorithm/other/?id=_846-%e4%b8%80%e6%89%8b%e9%a1%ba%e5%ad%90

---

• 时间复杂度
• 输出题解
• 是否最优解

[csming1995]

public class Solution {

    public boolean isNStraightHand(int[] hand, int W) {
        if (hand == null || W < 0 || W > hand.length) return false;

        if (hand.length % W != 0) return false;

        Map<Integer, Integer> hands = new TreeMap<>();
        for (int i : hand) {
            hands.put(i, hands.getOrDefault(i, 0) + 1);
        }

        Integer[] keyset = new Integer[hands.keySet().size()];
        hands.keySet().toArray(keyset);

        for (int i = 0; i < hands.keySet().size(); i++) {
            int num = keyset[i];
            int startTimes = hands.getOrDefault(num, 0);
            if (startTimes <= 0) {
                continue;
            }

            for (int j = 0; j < W; j++) {
                int times = hands.getOrDefault(num + j, 0);
                if (times < startTimes) return false;
                hands.put(num + j, times - startTimes);
            }
        }
        return true;
    }
}

[JalanJiang]

class Solution:
    def isNStraightHand(self, hand: List[int], W: int) -> bool:
        length = len(hand)
        # 无法整除直接返回 false
        if length % W != 0:
            return False
        
        # 排序
        hand.sort()
        
        # 初始化辅助空间
        hand_map = dict()
        
        for i in range(length):
            # 计数
            hand_map[hand[i]] = hand_map.get(hand[i], 0) + 1
        
        for i in range(length):
            h = hand[i]
            if hand_map[h] == 0:
                continue
            else:
                hand_map[h] -= 1
            for j in range(W - 1):
                h += 1
                if hand_map.get(h, 0) == 0:
                    return False
                else:
                    hand_map[h] -= 1
                
        return True

优化一下，一次取 n 张：

class Solution:
    def isNStraightHand(self, hand: List[int], W: int) -> bool:
        length = len(hand)
        # 无法整除直接返回 false
        if length % W != 0:
            return False
        
        # 初始化辅助空间
        hand_map = dict()
        
        for i in range(length):
            hand_map[hand[i]] = hand_map.get(hand[i], 0) + 1
        # 排序
        sort_hand = sorted(hand_map)
                    
        for h in sort_hand:
            if hand_map[h] == 0:
                continue
            elif hand_map[h] < 0:
                return False
            else:
                for i in range(1, W):
                    if hand_map.get(h + i, 0) == 0:
                        return False
                    else:
                        hand_map[h + i] -= hand_map[h]
            
        return True

[JalanJiang]

使用 Counter 实现

from collections import Counter

class Solution:
    def isNStraightHand(self, hand: List[int], W: int) -> bool:
        hand_counter = Counter(hand)
        # 按 key 值排序结果
        sort_hand = sorted(hand_counter)
         
        for h in sort_hand:
            # 牌不够取了
            if hand_counter[h] < 0:
                return False
            elif hand_counter[h] > 0:
                for i in range(1, W):
                    if hand_counter[h + i] == 0:
                        return False
                    else:
                        hand_counter[h + i] -= hand_counter[h]
            else:
                # == 0 时跳过
                continue
            
        return True

[JalanJiang]

• 时间复杂度
  • 排序复杂度 O(nlgn)
  • 循环复杂度 O(n)
• 空间复杂度 O(n)

[JalanJiang]

Done