Leetcode.914 卡牌分组

题目链接

Leetcode.914 卡牌分组 Rating ： 1371

题目描述

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

此时，你需要选定一个数字 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<=1041 <= deck.length <= 10^41<=deck.length<=104
• 0<=deck[i]<1040 <= deck[i] < 10^40<=deck[i]<104

解法：数论

一共有 $n$ 张牌。需要将其分为若干组，组内每张牌都相同，并且每一组有 X 张牌。

很显然 X 是 $n$ 的约数，即 $X\%n=0$。

假设给定的 $n$ 张牌，共有 $k$ 种牌，(cnt1,cnt2,cnt3,...,cntk−1,cntk)(cnt_1,cnt_2,cnt_3,...,cnt_{k-1},cnt_{k})(cnt1​,cnt2​,cnt3​,...,cntk−1​,cntk​)是每种牌的张数。那么很显然，X 也应该是这些 cnt1,cnt2,cnt3,...,cntk−1,cntk{cnt_1,cnt_2,cnt_3,...,cnt_{k-1},cnt_{k}}cnt1​,cnt2​,cnt3​,...,cntk−1​,cntk​ 的约数。 即，X=gcd{cnt1,cnt2,cnt3,...,cntk−1,cntk}X = gcd\\{ cnt_1,cnt_2,cnt_3,...,cnt_{k-1},cnt_{k} \\}X=gcd{cnt1​,cnt2​,cnt3​,...,cntk−1​,cntk​} 。

最后我们只需要判断是否 $X>=2$ 即可。

时间复杂度： $O(nlogC)$ C=max{cnt1,cnt2,cnt3,...,cntk−1,cntk}C = max\\{ cnt_1,cnt_2,cnt_3,...,cnt_{k-1},cnt_{k} \\}C=max{cnt1​,cnt2​,cnt3​,...,cntk−1​,cntk​}

C++代码：

class Solution {
public:bool hasGroupsSizeX(vector<int>& deck) {unordered_map<int,int> cnt;for(auto x:deck) cnt[x]++;int X = 0;for(auto [_,v]:cnt) X = gcd(X,v);return X >= 2;}
};