题目描述

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

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

示例 1：

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

示例 2：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hand-of-straights
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

• 今天的算法每日一题是数字排列题目，题意清晰明了，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。

• 根据题意，我们可以按照朴素的算法思想求解。朴素算法有很多的重复查找下一个元素是否存在的过程。我们可以使用 hashmap 存储元素和元素的出现次数，提升查询效率。具体实现如下：

通过代码

class Solution {
    public boolean isNStraightHand(int[] hand, int groupSize) {
        boolean ans = true;
        int n = hand.length;
        if (n % groupSize != 0) {
            ans = false;
            return ans;
        }

        Arrays.sort(hand);
        Map map = new HashMap<>(n);
        for (int i = 0; i < n; i++) {
            map.put(hand[i], map.getOrDefault(hand[i], 0) + 1);
        }

        for (int item : hand) {
            if (map.getOrDefault(item, 0) == 0) {
                continue;
            }

            for (int j = 0; j < groupSize; j++) {
                int next = item + j;
                if (map.getOrDefault(next, 0) > 0) {
                    map.put(next, map.getOrDefault(next, 0) - 1);
                } else {
                    ans = false;
                    return ans;
                }
            }
        }

        return ans;
    }
}

总结

• 上述算法的时间复杂度是O(n * n), 空间复杂度是O(n)

• 坚持算法每日一题，加油！