914. 卡牌分组——欧几里得算法

难度：简单

给定一副牌，每张牌上都写着一个整数。

此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：

每组都有 X 张牌。 组内所有的牌上都写着相同的整数。 仅当你可选的 X >= 2 时返回 true。

示例 ：

输入：[1,2,3,4,4,3,2,1]输出：true 解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]复制代码 Solution 通过组内所有的牌上都写着相同的整数这句话不难发现，能否成功分组和每次数组出现的次数有关，那是要每个数字出现的次数都相同吗？

不是

只要存在公约数就行。比如 1 有 2 个，2 有 4 个，也是可以的。

所以问题转换为求公约数。是一道数学问题

求公约数相信大家上学时都学过辗转相除法，也叫欧几里得算法，那该如何用程序实现呢？

请一定要记住这个模板。

// 辗转相除法private int gcd (int a, int b) {    return b == 0? a: gcd(b, a % b);}

复制代码代码中计数的方法也值得学习，巧用数组小标来计数，比使用 Map 简洁不少。

总之，这题要背下来。

Code/**

• @author 一条 coding*/class Solution {public boolean hasGroupsSizeX(int[] deck) {// 计数 int[] counter = new int[10000];for (int num: deck) {counter[num]++;}// 求 gcdint x = 0;for(int cnt: counter) {if (cnt > 0) {x = gcd(x, cnt);if (x == 1) {return false;}}}return x >= 2;}

• // 辗转相除法 private int gcd (int a, int b) {return b == 0? a: gcd(b, a % b);}}最后如果你觉得此文对你有一丁点帮助，点个赞。或者可以加入我的开发交流群：1025263163 相互学习，我们会有专业的技术答疑解惑

如果你觉得这篇文章对你有点用的话，麻烦请给我们的开源项目点点 star:http://github.crmeb.net/u/defu不胜感激 ！

PHP 学习手册：https://doc.crmeb.com技术交流论坛：https://q.crmeb.com