【算法面试】914. 卡牌分组——欧几里得算法

「这是我参与2022首次更文挑战的第3天，活动详情查看：2022首次更文挑战」

统计各个数出现的次数，然后求次数之间是否存在公约数

——leetcode此题热评

前言

大家好，我是一条，欢迎来到我的算法频道。

只做有趣的算法题，只为面试写算法。

Question

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]++;
        }
        // 求gcd
        int 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);
    }
}

最后

点赞，点赞，还TMD是点赞！