排序题目：一手顺子

题目

标题和出处

标题：一手顺子

出处：846. 一手顺子

难度

5 级

题目描述

要求

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

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

示例

示例 1：

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

示例 2：

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

数据范围

• $\text{1}\le \text{hand.length}\le {\text{10}}^{\text{4}}$
• $\text{0}\le \text{hand[i]}\le {\text{10}}^{\text{9}}$
• $\text{1}\le \text{groupSize}\le \text{hand.length}$

解法

思路和算法

由于题目要求将数组 $\text{hand}$ 中的牌分成若干组，每组的牌数都是 $\text{groupSize}$，因此只有当总牌数是 $\text{groupSize}$ 的倍数时才可能根据要求分组。如果总牌数不是 $\text{groupSize}$ 的倍数，则返回 $\text{false}$。

当总牌数是 $\text{groupSize}$ 的倍数时，遍历数组 $\text{hand}$ 并使用哈希表记录每个值的出现次数，然后将数组 $\text{hand}$ 排序，遍历排序后的数组判断是否可以根据要求分组。

遍历排序后的数组的过程中，对于遍历到的每个元素 $\text{start}$，如果 $\text{start}$ 在哈希表中记录的出现次数大于 $0$，则考虑以 $\text{start}$ 作为一个分组的最小值，判断剩余的牌是否可以组成 $[\text{start},\text{start}+\text{groupSize}-1]$ 的分组。具体做法如下。

1. 从 $\text{start}$ 到 $\text{start}+\text{groupSize}-1$ 的每个整数的计数都应该大于 $0$，如果该范围内存在一个整数的计数是 $0$，则无法组成 $[\text{start},\text{start}+\text{groupSize}-1]$ 的分组，返回 $\text{false}$。

2. 对于从 $\text{start}$ 到 $\text{start}+\text{groupSize}-1$ 的每个整数 $\text{val}$，将 $\text{val}$ 在哈希表中的计数减 $1$。

遍历结束之后，如果没有遇到不可以完成分组的情况，则返回 $\text{true}$。

上述解法的正确性说明如下。

1. 遍历排序后的数组的过程中，遍历元素的顺序是从小到大，因此当遍历到元素 $\text{start}$ 时，小于 $\text{start}$ 的元素都已经遍历过并完成分组，$\text{start}$ 是尚未分组的最小值，$\text{start}$ 一定是一个分组中的最小值。

2. 由于已知 $\text{start}$ 一定是一个分组中的最小值，因此该分组的取值范围是 $[\text{start},\text{start}+\text{groupSize}-1]$，只有当该范围内的每个值都存在时才可能完成分组。

代码

class Solution {public boolean isNStraightHand(int[] hand, int groupSize) {int length = hand.length;if (length % groupSize != 0) {return false;}Map<Integer, Integer> counts = new HashMap<Integer, Integer>();for (int val : hand) {counts.put(val, counts.getOrDefault(val, 0) + 1);}Arrays.sort(hand);for (int i = 0; i < length; i++) {int start = hand[i];if (!counts.containsKey(start)) {continue;}for (int j = 0; j < groupSize; j++) {int val = start + j;if (!counts.containsKey(val)) {return false;}counts.put(val, counts.get(val) - 1);if (counts.get(val) == 0) {counts.remove(val);}}}return true;}
}

复杂度分析

• 时间复杂度：$O(n\log n)$，其中 $n$ 是数组 $\text{hand}$ 的长度。排序需要 $O(n\log n)$ 的时间，遍历数组更新哈希表需要 $O(n)$ 的时间，时间复杂度是 $O(n\log n)$。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\text{hand}$ 的长度。需要使用哈希表记录每个值的出现次数，哈希表的空间是 $O(n)$，排序需要 $O(\log n)$ 的递归调用栈空间，空间复杂度是 $O(n)$。