简单

问题描述

给你一个整数 n。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和（每一位上的数字相加），然后把数位和相等的数字放到同一个组中。

请你统计每个组中的数字数目，并返回数字数目并列最多的组有多少个。

示例 1：

输入：n = 13
输出：4
解释：总共有 9 个组，将 1 到 13 按数位求和后这些组分别是：
[1,10]，[2,11]，[3,12]，[4,13]，[5]，[6]，[7]，[8]，[9]。总共有 4 个组拥有的数字并列最多。

示例 2：

输入：n = 2
输出：2
解释：总共有 2 个大小为 1 的组 [1]，[2]。

示例 3：

输入：n = 15
输出：6

示例 4：

输入：n = 24
输出：5

提示：

• 1 <= n <= 104

哈希表

由于 $n$ 最大取值为 $10^4$，因此最大数位和为 $9 \times 4 = 36$，可以建立一个长度为 $37$ 的数组，用于记录数位和为对应下标的数字个数，最终统计数组最大值的个数即为答案。

/**
 * @param {number} n
 * @return {number}
 */
var countLargestGroup = function (n) {
  const arr = new Array(40).fill(0)
  let max = 0
  for (let i = 1; i <= n; i++) {
    let num = i
    let cnt = 0
    while (num / 10) {
      cnt += num % 10
      num = ~~(num / 10)
    }
    max = Math.max(max, ++arr[cnt])
  }
  let ans = 0
  for (let i = 0; i < 40; i++) {
    if (arr[i] === max) {
      ans++
    }
  }
  return ans
}

• 时间复杂度：$O(n \log {n})$
• 空间复杂度：$O(C)$，$n$ 最大取值 $10^5$，$9999 = 4 \times 9 = 36$，所以 $C$ 最大不超过 $37$