题目描述

爱丽丝有一手（hand）由整数数组给定的牌。 

现在她想把牌重新排列成组，使得每个组的大小都是 W，且由 W 张连续的牌组成。

如果她可以完成分组就返回 true，否则返回 false。

样例1

输入：hand = [1,2,3,6,2,3,4,7,8], W = 3
输出：true
解释：爱丽丝的手牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。

样例2

输入：hand = [1,2,3,4,5], W = 4
输出：false
解释：爱丽丝的手牌无法被重新排列成几个大小为 4 的组。

提示

• 1 <= hand.length <= 10000
• 0 <= hand[i] <= 10^9
• 1 <= W <= hand.length

算法1

(平衡树)

• 把所有的元素按序存到TreeMap中，每次贪心的取最小的元素进行判断是否能形成一个长度为W的连续序列，并且把判断后的数字全部删除，直到平衡树空为止。

• 时间复杂度：$O(nlogn)$

Java 代码

class Solution {
    public boolean isNStraightHand(int[] hand, int W) {
        TreeMap<Integer,Integer> map = new TreeMap<>();
        for(int x: hand) map.put(x, map.getOrDefault(x, 0) + 1);
        while(map.size() > 0){
            int begin = map.firstKey();
            for(int i = begin; i < begin + W; i++){
                if(!map.containsKey(i)) return false;
                map.put(i, map.get(i) - 1);
                if(map.get(i) == 0) map.remove(i);
            }
        }
        return true;
    }
}