「每日LeetCode」2021年4月1日

本文最后更新于：2023年3月19日 晚上

Lt1399. 统计最大组的数目

1399. 统计最大组的数目

给你一个整数 n 。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和（每一位上的数字相加），然后把数位和相等的数字放到同一个组中。
请你统计每个组中的数字数目，并返回数字数目并列最多的组有多少个。
 示例 1：

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

示例 2：

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

示例 3：

1
2
输入：n = 15
输出：6

示例 4：

1
2
输入：n = 24
输出：5

提示：

  • 1 <= n <= 10^4

思路

先生成数组，借助 map，记录每一个数位和相同的数字组成的数组，按照数组的长度降序排序，开始计数，直到当前数组长度不等于上一个数组长度，返回 count。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number} n
 * @return {number}
 */
var countLargestGroup = function (n) {
  const arr = new Array(n).fill("").map((e, index) => index + 1);
  const map = new Map();
  for (const num of arr) {
    const sum =
      (num + "").split("").reduce((a, b) => Number(a) + Number(b)) + "";
    if (map.has(sum)) map.set(sum, [...map.get(sum), num]);
    else map.set(sum, [num]);
  }
  let count = 0,
    prev = null;
  for (const e of [...map.values()].sort((a, b) => b.length - a.length)) {
    if (!prev) prev = e.length;
    if (prev !== e.length) return count;
    count++;
  }
  return count;
};