算法题 卡牌分组

914. 卡牌分组

问题描述

给定一副卡牌，每张卡牌上有一个整数。你需要判断是否可以将这些卡牌分成若干组，使得：

• 每组至少有2张卡牌
• 每组中的所有卡牌上的数字都相同

示例：

输入: deck = [1,2,3,4,4,3,2,1] 输出: true 解释: 可能的分组是 [1,1], [2,2], [3,3], [4,4] 输入: deck = [1,1,1,2,2,2,3,3] 输出: false 解释: 没有办法将卡牌分成满足要求的组。 输入: deck = [1] 输出: false 解释: 卡牌数量少于2，无法分组。

算法思路

最大公约数：

1. 统计每个数字出现的频次
2. 所有频次的最大公约数必须大于等于2
3. 如果最大公约数 ≥ 2，说明可以将所有频次都分成大小为最大公约数的组

代码实现

方法一：最大公约数 + HashMap

classSolution{/** * 判断卡牌是否可以按要求分组 * * @param deck 卡牌数组，每个元素表示卡牌上的数字 * @return 如果可以分组返回true，否则返回false */publicbooleanhasGroupsSizeX(int[]deck){// 边界情况：卡牌数量少于2if(deck.length<2){returnfalse;}// 统计每个数字的出现频次Map<Integer,Integer>countMap=newHashMap<>();for(intcard:deck){countMap.put(card,countMap.getOrDefault(card,0)+1);}// 获取所有频次值intgcdValue=-1;for(intcount:countMap.values()){if(gcdValue==-1){gcdValue=count;}else{gcdValue=gcd(gcdValue,count);// 如果最大公约数已经变成1，可以提前返回if(gcdValue==1){returnfalse;}}}// 所有频次的最大公约数必须大于等于2returngcdValue>=2;}/** * 计算两个数的最大公约数（欧几里得算法） * * @param a 第一个数 * @param b 第二个数 * @return 最大公约数 */privateintgcd(inta,intb){while(b!=0){inttemp=b;b=a%b;a=temp;}returna;}}

方法二：Stream API

classSolution{/** * 使用Java 8 Stream API * * @param deck 卡牌数组 * @return 如果可以分组返回true，否则返回false */publicbooleanhasGroupsSizeX(int[]deck){if(deck.length<2){returnfalse;}// 统计频次并计算GCDMap<Integer,Long>countMap=Arrays.stream(deck).boxed().collect(Collectors.groupingBy(Function.identity(),Collectors.counting()));longgcdValue=countMap.values().stream().reduce(-1L,(a,b)->a==-1?b:gcd(a,b));returngcdValue>=2;}privatelonggcd(longa,longb){while(b!=0){longtemp=b;b=a%b;a=temp;}returna;}}

算法分析

• 时间复杂度：O(n + m log k)
  • n 是卡牌总数
  • m 是不同数字的个数
  • k 是最大频次值
  • 最大公约数计算的时间复杂度为 O(log k)
• 空间复杂度：
  • 方法一：O(m)，m为不同数字的个数
  • 方法二：O(maxCard)，maxCard为卡牌上的最大数字

算法过程

输入：deck = [1,2,3,4,4,3,2,1]

1. 统计频次：{1:2, 2:2, 3:2, 4:2}
2. 计算最大公约数：
   • 初始gcdValue = 2
   • gcd(2, 2) = 2
   • gcd(2, 2) = 2
   • gcd(2, 2) = 2
3. 最终gcdValue = 2 >= 2，返回true

输入：deck = [1,1,1,2,2,2,3,3]

1. 统计频次：{1:3, 2:3, 3:2}
2. 计算最大公约数：
   • 初始gcdValue = 3
   • gcd(3, 3) = 3
   • gcd(3, 2) = 1
3. 最终gcdValue = 1 < 2，返回false

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[]deck1={1,2,3,4,4,3,2,1};System.out.println("Test 1: "+solution.hasGroupsSizeX(deck1));// true// 测试用例2：无法分组int[]deck2={1,1,1,2,2,2,3,3};System.out.println("Test 2: "+solution.hasGroupsSizeX(deck2));// false// 测试用例3：单张卡牌int[]deck3={1};System.out.println("Test 3: "+solution.hasGroupsSizeX(deck3));// false// 测试用例4：两张相同卡牌int[]deck4={1,1};System.out.println("Test 4: "+solution.hasGroupsSizeX(deck4));// true// 测试用例5：所有卡牌相同int[]deck5={1,1,1,1,1,1};System.out.println("Test 5: "+solution.hasGroupsSizeX(deck5));// true// 测试用例6：频次互质int[]deck6={1,1,2,2,2,2};System.out.println("Test 6: "+solution.hasGroupsSizeX(deck6));// true// 测试用例7：频次为质数int[]deck7={1,1,1,1,2,2,2,2,2,2};System.out.println("Test 7: "+solution.hasGroupsSizeX(deck7));// true// 测试用例8：包含0int[]deck8={0,0,1,1,1,1,2,2,2,2,2,2};System.out.println("Test 8: "+solution.hasGroupsSizeX(deck8));// true// 测试用例9：大数值int[]deck9={1000,1000,1000,1000,1000,1000};System.out.println("Test 9: "+solution.hasGroupsSizeX(deck9));// true}

关键点

1. 最大公约数：

   • 所有频次必须有一个公共因子 ≥ 2
   • 这个公共因子就是所有频次的最大公约数

2. 边界处理：

   • 卡牌总数 < 2 时直接返回 false

常见问题

1. 为什么最大公约数 ≥ 2 ？
   • 如果最大公约数 = g ≥ 2，那么每个频次都可以被g整除
   • 每个数字可以分成count/g组，每组g张卡牌