LeetCode 914. X of a Kind in a Deck of Cards

You are given an integer array deck where deck[i] represents the number written on the ith card.

Partition the cards into one or more groups such that:

• Each group has exactly x cards where x > 1, and
• All the cards in one group have the same integer written on them.

Return true if such partition is possible, or false otherwise.

Example 1:

Input: deck = [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4].

Example 2:

Input: deck = [1,1,1,2,2,2,3,3]
Output: false
Explanation: No possible partition.

Constraints:

• 1 <= deck.length <= 104
• 0 <= deck[i] < 104

---

读题读了半天还读错了……其实是求，把一个数组里的数字分成数字相等的n组，每组的数字个数也要一样，那么它的本质就是求这个数组里每个数字出现次数的最大公约数。

第一种方法是brute force，不用gcd的求法，就直接从最小的count遍历到2，看能不能被所有的count整除。

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : deck) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        int min = 10000;
        for (int i : map.keySet()) {
            min = Math.min(min, map.get(i));
        }
        for (int i = min; i >= 2; i--) {
            boolean found = true;
            for (int num : map.keySet()) {
                int value = map.get(num);
                if (value % i != 0) {
                    found = false;
                    continue;
                }
            }
            if (found) {
                return true;
            }
        }
        return false;
    }
}

gcd的求法已经忘了。回顾了一下，大概就是gcd(a, b)，如果b == 0那么a就是gcd，要么就把a变成b，b变成a%b，继续recursive gcd。

Java Program to Compute GCD - GeeksforGeeks

对应到这道题上，就是计算完count以后遍历map，先全局记一个gcd，每次计算全局gcd和当前遍历到的数字的gcd，最后看全局gcd是否>=2。

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : deck) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        
        int g = -1;
        for (int i : map.keySet()) {
            int value = map.get(i);
            if (g == -1) {
                g = value;
            } else {
                g = gcd(g, value);
            }
        }
        return g >= 2;
    }
 
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
}