一副牌中的 X 种类型

问题陈述

我们得到一个整数数组 deck，其中 deck[i] 代表第 i 张牌上的数字。

将这些牌分成一个或多个组，使得：

每组恰好有 x 张牌，其中 x > 1，并且

一组中的所有牌都具有相同的整数。

如果可以进行这样的划分，则返回 true，否则返回 false。

Java 实现

使用计数数组方法的 Java 实现

输出

代码解释

• hasGroupsSizeX 方法检查是否可以将一副牌分成若干组，每组牌的数量相同。它利用一个数组（count）来记录每张牌的频率。GCD 方法计算两个数字的最大公约数（GCD）。
• 该算法迭代遍历频率，动态更新 GCD。如果最终 GCD 大于或等于 2，则表示牌可以分组为至少大小为 2 的集合。该解决方案确保每组都有一个公约数，从而促进等大小分组。

时间复杂度

• N 是牌组中的牌数，时间复杂度为 O(N)。GCD 计算在循环中完成，对于给定的输入，需要 O(logmin (a, b)) 的时间。

空间复杂度

• 空间复杂度为 1，因为存储所有内容所需的内存大小是恒定的。该算法使用一个长度为 1000 的恒定大小的计数数组来建立每张牌的频率，gcd 函数仅使用线性空间。

使用 HashMap 的 Java 方法

输出

代码解释

• Java 中的算法提供了一个答案，说明一个数组是否可以划分为大小超过 1 的组。hasGroupsSizeX 方法始终包含用于存储每个元素频率的哈希映射。它通过使用 hcf 计算这些频率的最大公约数 (GCD)，然后使用最佳拟合算法来完成。
• GCD 显示了有多少人——最大的数字——可以属于该组。如果 GCD 大于或等于 2，则表示存在组大小，因此该方法返回 true，但如果小于 2，则返回 false。

时间复杂度

• hasGroupsSizeXs 的组织操作需要恒定的时间，O(N)，其中 arr 的大小为 N。

空间复杂度

• 空间也为 O(N)。它使用哈希映射来存储每个元素的频率差，以及数组 A 的大小被添加到其中。