0914-卡牌分组

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

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

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

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

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

示例 1：

**输入：** deck = [1,2,3,4,4,3,2,1]
**输出：** true
**解释：** 可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]

示例 2：

**输入：** deck = [1,1,1,2,2,2,3,3]
**输出：** false
**解释：** 没有满足要求的分组。

提示：

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

方法一：暴力

思路

我们枚举所有可行的 X，判断是否有满足条件的 X 即可。

算法

我们从 2 开始，从小到大枚举 X。

由于每一组都有 X 张牌，那么 X 必须是卡牌总数 N 的约数。

其次，对于写着数字 i 的牌，如果有 count}_i 张，由于题目要求「组内所有的牌上都写着相同的整数」，那么 X 也必须是 count}_i 的约数，即：

\textit{count}_i \bmod X == 0

所以对于每一个枚举到的 X，我们只要先判断 X 是否为 N 的约数，然后遍历所有牌中存在的数字 i，看它们对应牌的数量 count}_i 是否满足上述要求。如果都满足等式，则 X 为符合条件的解，否则需要继续令 X 增大，枚举下一个数字。

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        int N = deck.length;
        int[] count = new int[10000];
        for (int c: deck) {
            count[c]++;
        }

        List<Integer> values = new ArrayList<Integer>();
        for (int i = 0; i < 10000; ++i) {
            if (count[i] > 0) {
                values.add(count[i]);
            }
        }

        for (int X = 2; X <= N; ++X) {
            if (N % X == 0) {
                boolean flag = true;
                for (int v: values) {
                    if (v % X != 0) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    return true;
                }
            }
        }

        return false;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        count = collections.Counter(deck)
        N = len(deck)
        for X in range(2, N + 1):
            if N % X == 0:
                if all(v % X == 0 for v in count.values()):
                    return True
        return False
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    int count[10000];
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        int N = (int)deck.size();
        for (int c: deck) count[c]++;

        vector<int> values;
        for (int i = 0; i < 10000; ++i) {
            if (count[i] > 0) {
                values.emplace_back(count[i]);
            }
        }

        for (int X = 2; X <= N; ++X) {
            if (N % X == 0) {
                bool flag = 1;
                for (int v: values) {
                    if (v % X != 0) {
                        flag = 0;
                        break;
                    }
                }
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }
};

复杂度分析

  • 时间复杂度：O(N^2)，其中 N 是卡牌个数。最多枚举 N 个可能的 X，对于每个 X，要遍历的数字 i 最多有 N 个。

  • 空间复杂度：O(N + C) 或 O(N)，其中 C 是数组 deck 中数的范围，在本题中 C 的值为 10000。在 C++ 和 Java 代码中，我们先用频率数组 count 存储了每个数字 i 出现的次数 count}[i]，随后将所有超过零的次数转移到数组 values 中，方便进行遍历，因此需要使用长度为 C 的 count 数组以及长度不超过 N 的 values 数组，空间复杂度为 O(N + C)。在 Python 代码中，我们直接使用哈希映射存储每个数字 i 以及出现的次数，因此空间复杂度为 O(N)。

方法二：最大公约数

思路和算法

由于方法一已经提及 X 一定为 count}_i 的约数，这个条件是对所有牌中存在的数字 i 成立的，所以我们可以推出，只有当 X 为所有 count}_i 的约数，即所有 count}_i 的最大公约数的约数时，才存在可能的分组。公式化来说，我们假设牌中存在的数字集合为 a, b, c, d, e，那么只有当 X 为

gcd(\textit{count}_a,\textit{count}_b,\textit{count}_c,\textit{count}_d,\textit{count}_e)

的约数时才能满足要求。

因此我们只要求出所有 count}_i 最大公约数 g，判断 g 是否大于等于 2 即可，如果大于等于 2，则满足条件，否则不满足。

[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        int[] count = new int[10000];
        for (int c: deck) {
            count[c]++;
        }

        int g = -1;
        for (int i = 0; i < 10000; ++i) {
            if (count[i] > 0) {
                if (g == -1) {
                    g = count[i];
                } else {
                    g = gcd(g, count[i]);
                }
            }
        }
        return g >= 2;
    }

    public int gcd(int x, int y) {
        return x == 0 ? y : gcd(y % x, x);
    }
}
[sol2-Python3]
1
2
3
4
class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        vals = collections.Counter(deck).values()
        return reduce(gcd, vals) >= 2
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int cnt[10000];
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        for (auto x: deck) cnt[x]++;
        int g = -1;
        for (int i = 0; i < 10000; ++i) {
            if (cnt[i]) {
                if (~g) {
                    g = gcd(g, cnt[i]);
                } else {
                    g = cnt[i];
                }
            }
        }
        return g >= 2;
    }
};

复杂度分析

  • 时间复杂度：O(N \log C)，其中 N 是卡牌的个数，C 是数组 deck 中数的范围，在本题中 C 的值为 10000。求两个数最大公约数的复杂度是 O(\log C)，需要求最多 N - 1 次。

  • 空间复杂度：O(N + C) 或 O(N)。

 Comments
On this page
0914-卡牌分组