914_x_of_a_kind_in_a_deck_of_cards

914. 卡牌分组 简单

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：[1]
输出：false
解释：没有满足要求的分组。

示例 4：

输入：[1,1]
输出：true
解释：可行的分组是 [1,1]

示例 5：

输入：[1,1,2,2,2,2]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[2,2]

提示：

1. 1 <= deck.length <= 10000
2. 0 <= deck[i] < 10000

代码参考：

package main

import "fmt"

func main() {
    fmt.Println(hasGroupsSizeX([]int{1, 1, 1, 2, 2, 2, 3, 3}))       // false
    fmt.Println(hasGroupsSizeX([]int{1, 1, 1, 1, 2, 2, 2, 2, 2, 2})) // true

}

// 统计各个数字出现的频率，看下频率之间是否能分组（存在公约数）
// 关键要理解分组等价于是否存在公约数
func hasGroupsSizeX(deck []int) bool {
    if len(deck) <= 1 {
        return false
    }

    freqs := make(map[int]int)
    for _, num := range deck {
        freqs[num]++
    }

    counts := make([]int, 0, len(freqs))
    for _, freq := range freqs {
        counts = append(counts, freq)
    }

    for i := 0; i < len(counts)-1; i++ {
        if gcd(counts[i], counts[i+1]) == 1 { // 不能分组
            return false
        }
    }

    return true
}

// 辗转相除法求最大公约数
func gcd(x, y int) int {
    // for y != 0 {
    //     x, y = y, x%y
    // }
    // return x

    if y == 0 {
        return x
    }
    return gcd(y, x%y)
}