原创

每日一题-914. 卡牌分组

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

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

每组都有 X 张牌。 组内所有的牌上都写着相同的整数。 仅当你可选的 X >= 2 时返回 true。

示例 1:

              
  • 1
  • 2
  • 3
输入:[1,2,3,4,4,3,2,1] 输出:true 解释:可行的分组是 [1,1][2,2][3,3][4,4]

示例 2:

              
  • 1
  • 2
  • 3
输入:[1,1,1,2,2,2,3,3] 输出:false 解释:没有满足要求的分组。

示例 3:

              
  • 1
  • 2
  • 3
输入:[1] 输出:false 解释:没有满足要求的分组。

示例 4:

              
  • 1
  • 2
  • 3
输入:[1,1] 输出:true 解释:可行的分组是 [1,1]

示例 5:

              
  • 1
  • 2
  • 3
  • 4
输入:[1,1,2,2,2,2] 输出:true 解释:可行的分组是 [1,1][2,2][2,2]

提示:

1 <= deck.length <= 10000

0 <= deck[i] < 10000

解题思路

由于每组的牌都是相等的,那么X必须是牌总数N的约数。

另外,从示例5可以看到,对于数字i 的总数count(i), X不一定等于 count(i), 还有可能是count(i)的约数。

所以,从上面可以看出来, X必须是对于每个出现的数 i的总数 count(i) 的约数,那么这可以看作 X是所有 count(i) 的的最大公约数的约数。

知道了这个,就只需要把代码写出来了

              
  • 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
/** * @param {number[]} deck * @return {boolean} */ var hasGroupsSizeX = function (deck) { // 求最大公约数 var gcd = function (x, y) { return x == 0 ? y : gcd(y % x, x); } var count = (new Array(10000)).fill(0); // 获取每个数的数量 for (var index = 0; index < deck.length; index++) { count[deck[index]]++; } var g = -1; for (var index = 0; index < 10000; index++) { if (count[index] > 0) { if (g === -1) g = count[index]; else // 求每个数的数量与上个数的数量的最大公约数 g = gcd(g, count[index]); } } return g >= 2; };

本文于   2020/3/27 下午  发布在  数学与算法  分类下,当前已被围观  77  次

相关标签: 算法与数学 每日一题

永久地址: https://huhuang.net/article/7

版权声明: 自由转载-署名-非商业性使用   |   Creative Commons BY-NC 3.0 CN