846. 一手顺子

Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。

给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌，和一个整数 groupSize 。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

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

提示：

  • 1 <= hand.length <= 104
  • 0 <= hand[i] <= 109
  • 1 <= groupSize <= hand.length

算法思想：

  • 如果数组长度不能被顺子长度等分，则直接不符合
  • 然后将数组进行从小到大排序
  • 将数组元素存入哈希表并记录出现次数
  • 每次取出最小元素x当做顺子的头，然后在哈希表中读取当前顺子的其余元素
  • 如果可以满足要求，则当前顺子的其余元素在哈希表中的值都必须大于等于1
  • 如果值小于1则不满足

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public boolean isNStraightHand(int[] hand, int groupSize) {
    int len = hand.length;
    //如果当前数组长度不能被groupSize均分，则直接返回false
    if (len % groupSize != 0) {
        return false;
    }
    //数组排序，每次找出最小元素
    Arrays.sort(hand);

    HashMap<Integer, Integer> map = new HashMap<>();

    for (int x : hand) {
        map.put(x, map.getOrDefault(x, 0) + 1);
    }


    for (int x : hand) {
        //找出顺子的开头
        if (!map.containsKey(x)) {
            continue;
        }


        for (int i = 0; i < groupSize; i++) {
            //判断以x开头的当前顺子组的元素
            int num = x + i;
            //如果后续元素不存在，直接返回false
            if (!map.containsKey(num)) {
                return false;
            }

        
            //存在，更新记录
            map.put(num, map.get(num) - 1);
            //如果当前数字出现次数已经为0，则移除
            if (map.get(num) == 0) {
                map.remove(num);
            }

        }


    }


    return true;
}