LeetCode——卡牌分组

NO.914 卡牌分组简单

思路一：暴力 遍历统计每个数字的个数，然后找到最小的数量min，然后遍历[2,min]是否存在可以整除其他已统计好的数字的数量的整数。

两个剪枝的点：如果最小数量min<2，则[2,min]区间不存在元素，即不能满足要求。[2,min]区间内被遍历到的整数如果不能整除deck.length则不能成功分组，应跳过。

public boolean hasGroupsSizeX(int[] deck) {
    //统计数字出现的个数
    int[] counter = new int[10000];
    for (int e : deck) {
        counter[e]++;
    }
    //找到数量最少的卡牌
    int min = 10000;
    List<Integer> values=new ArrayList<>();
    for (int e : counter) {
        if (e > 0) {
            values.add(e);
            min=Math.min(e,min);
        }
    }
    //如果最少的数量小于2，返回false
    if (min<2)return false;
    //遍历[2,min]区间
    for (int x=2;x<=min;x++){
        //如果x不能整除length则跳过
        if (deck.length%x!=0)continue;
        //检查x是否能整除每个数字的数量
        if (isOK(values,x))return true;
    }
    return false;
}

private boolean isOK(List<Integer> values, int x) {
    for (int value : values) {
        //如果有不能被x整除的数量就返回false
        if (value%x!=0)return false;
    }
    return true;
}

时间复杂度：O(n^2) n是卡牌数量。最多有n种x，每个x检测最多遍历检测n次。

思路二：GCD 观察上述实现思路总结其实就是：找到一个可以整除每个数量的x。这个符合要求的x不就是每个数量的最大公约数么。所以统计每个数字的数量之后，两两一次求GCD即可。

public boolean hasGroupsSizeX(int[] deck) {
    //计数
    int[] counter = new int[10000];
    for (int e : deck) {
        counter[e]++;
    }
    //求GCD
    int x = 0;
    for (int value : counter) {
        if (value > 0) {
            if (x==0)x=value;
            else x=gcd(x,value);
        }
    }
    return x>=2;
}

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

时间复杂度：O(nlogn) n是卡牌数量。求GCD时间logn。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.914 卡牌分组 简单

NO.914 卡牌分组简单