[Leedcode][JAVA][第914题][最大公约数]

【问题描述】

给定一副牌，每张牌上都写着一个整数。此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：每组都有 X 张牌。 组内所有的牌上都写着相同的整数。 仅当你可选的 X >= 2 时返回 true。示例 1：输入：[1,2,3,4,4,3,2,1] 输出：true 解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4] 示例 2：输入：[1,1,1,2,2,2,3,3] 输出：false 解释：没有满足要求的分组。 示例 3：输入：[1] 输出：false 解释：没有满足要求的分组。 示例 4：输入：[1,1] 输出：true 解释：可行的分组是 [1,1] 示例 5：输入：[1,1,2,2,2,2] 输出：true 解释：可行的分组是 [1,1]，[2,2]，[2,2]提示：1 <= deck.length <= 10000 0 <= deck[i] < 10000

【解答思路】

1. 时间复杂度：O(N) 空间复杂度：O(N)

• 遍历一次，统计每个数值的个数，如果某个数值只有 1 个，直接返回 false；
• 输入 [2, 2, 2, 2, 3, 3, 3, 3, 3, 3]，其实也是符合题意的分组，2 有 4个，3 有 6 个，相同的 2 和 3 都需要拆成 2 个一组，即需要求两两元素个数的公约数是否有共同的公约数。

public boolean hasGroupsSizeX(int[] deck) {//计数 int[] cnt = new int[10000];for(int x: deck){cnt[x]++; }//避免虚幻内赋值int a= cnt[0];for(int i: cnt){//出现单个返回错误if(i==1){return false;}if(i>1){//循环计算最大公约数a = gcd(a,i);if(a ==1 ){return false;}}}return true;}/*最大公约数12 ➗ 9 = 1 ...... 39 ➗ 3 = 3 ...... 03返回 0跳出循环*/public int gcd(int x, int y){int max = Math.max(x,y);int min = Math.min(x,y);while(min!= 0){int temp =min;min = max% min;max = temp;}return max;/* //递归求最大公约数（伟哥提供） private int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);}} 作者：liweiwei1419 链接：https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/solution/qiu-jie-zui-da-gong-yue-shu-java-by-liweiwei1419/

​###### 2. 甜姨的精简操作
2.1 3ms的刀法

class Solution {public boolean hasGroupsSizeX(int[] deck) {// 计数int[] counter = new int[10000];for (int num: deck) {counter[num]++;}// 迭代求多个数的最大公约数int x = 0;for(int cnt: counter) {if (cnt > 0) {x = gcd(x, cnt); if (x == 1) { // 如果某步中gcd是1，直接返回falsereturn false;}}}return x >= 2;}// 辗转相除法private int gcd (int a, int b) {return b == 0? a: gcd(b, a % b);} }作者：sweetiee 链接：https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/solution/3ms-jian-dan-java-fu-zeng-reducexie-fa-miao-dong-b/

2.2 迭代求gcd的过程可以用reduce算子进行代码简化

class Solution {public boolean hasGroupsSizeX(int[] deck) {// 计数int[] counter = new int[10000];for (int num: deck) {counter[num]++;}// reduce求多个数的最大公约数// （因为这里当gcd==1的时候没有提前终止，并且本题数据量太小无法用并行流，因此耗时10ms，比for循环慢点）return Arrays.stream(counter).reduce(this::gcd).getAsInt() >= 2;}// 辗转相除法private int gcd (int a, int b) {return b == 0? a: gcd(b, a % b);} }作者：sweetiee 链接：https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/solution/3ms-jian-dan-java-fu-zeng-reducexie-fa-miao-dong-b/

其中，reduce(this::gcd) 即为 reduce((a, b) -> gcd(a, b))
下图以reduce((a, b) -> a + b)来解释reduce算子：

【总结】

1.求最大公约数（辗转相除法）

public int gcd(int x, int y){int max = Math.max(x,y);int min = Math.min(x,y);while(min!= 0){int temp =min;min = max% min;max = temp;}return max; private int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);} private int gcd (int a, int b) {return b == 0? a: gcd(b, a % b);

统计个数的时候，可以使用哈希表，也可以使用数组。

• 看题目中的数据范围，如果题目中说，输入数据只包含小写字母（大写字符）使用数组统计是相对方便的
• 哈希表底层也是数组。使用数组做计数任务其实是自己编写了哈希函数

变量名称只有少数几个词可以写缩写用，一般情况下，都用全称。

• cnt 表示 count， res 表示 result ，ans 表示 answer

总结

以上是生活随笔为你收集整理的[Leedcode][JAVA][第914题][最大公约数]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。