leedcode：卡牌分组

3.27日：卡牌分组

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

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

• 每组都有x张牌
• 组内所有的牌上都写着相同的整数

仅当你可选的x>=2时返回true。

思路：

1、遍历一次，统计每个数值的个数，如果某个数值只有一个，直接返回false。

2、可以看一下示例5，将[2,2,2,2]分为了两组，显然2是公约数。

public class Solution{
    public boolean hasGroupSizeX(int[] deck){
    int len = deck.length;if(len < 2){
    return false;}//用于计数的数组，10000是题目给出的数值范围int[] count = new int[10000];for (int num : deck){
    count[num]++;}//先得到第一个数的个数，避免在循环中赋值int x = count[deck[0]];for (int i = 0;i < 10000; i++){
    if (count[i] == 1){
    return false:}if (count[i] > 1){
    x = gcd(x,count[i]);}}return true;}//最小公约数public int gcd(int a,int b){
    return b == 0? a: gcd(b, a % b);}//Mainpublic static void main(String[] args) {
    Solution solution = new Solution();int[] deck = new int[]{
    0, 0, 1, 1, 1, 1, 2, 2, 3, 4};System.out.println(solution.gcd(2, 8));}
}

附：最大公约数求法

第一种：更相减损法

int gcd(int a,int b){
    if (a == b){
    return a;}if (a > b){
    return gcd(a-b,b);}if (a < b){
    return gcd(b-a,a);}
}

第二种：辗转相除法

int gcd (int a,int b){
    return b == 0? a: gcd(b, a % b);
}