【LetMeFly】1399.统计最大组的数目：哈希表模拟（简单题简单做）
力扣题目链接：https://leetcode.cn/problems/count-largest-group/
给你一个整数 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
提示：
解题方法：哈希表
如何统计一个数字十进制下的每一位之和？
在这个数字(假设为$t$)不为0时，不断累加这个数的个位（$t%10$），并将这个数除以$10$（向下取整）。
使用一个哈希表，键为“一个数的每一位之和”，值为这个“和”的出现次数。
统计最大的“值”，然后统计有多少个键值对的值是这个最大的值。
- 时间复杂度$O(n\log_{10}n)$
- 空间复杂度$O(n)$
AC代码
C++
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
27
|
class Solution {
public:
int countLargestGroup(int n) {
unordered_map<int, int> bin;
int maxTimes = 0;
for (int i = 1; i <= n; i++) {
int cnt = 0, temp = i;
while (temp) {
cnt += temp % 10;
temp /= 10;
}
maxTimes = max(maxTimes, ++bin[cnt]);
}
int ans = 0;
for (auto [a, b] : bin) {
ans += b == maxTimes;
}
return ans;
}
};
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| '''
Author: LetMeFly
Date: 2025-04-23 13:20:37
LastEditors: LetMeFly.xyz
LastEditTime: 2025-04-23 13:22:37
'''
from collections import defaultdict
class Solution:
def countLargestGroup(self, n: int) -> int:
counter = defaultdict(int)
maxTimes = 0
for i in range(1, n + 1):
cnt = sum(map(int, str(i)))
counter[cnt] += 1
maxTimes = max(maxTimes, counter[cnt])
return sum(b == maxTimes for a, b in counter.items())
|
Java
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
27
28
29
30
|
import java.util.Map;
import java.util.HashMap;
class Solution {
public int countLargestGroup(int n) {
Map<Integer, Integer> times = new HashMap<>();
int maxTimes = 0;
for (int i = 1; i <= n; i++) {
int cnt = 0, temp = i;
while (temp > 0) {
cnt += temp % 10;
temp /= 10;
}
maxTimes = Math.max(maxTimes, times.merge(cnt, 1, Integer::sum));
}
int ans = 0;
for (Map.Entry<Integer, Integer> pair : times.entrySet()) {
if (pair.getValue() == maxTimes) {
ans++;
}
}
return ans;
}
}
|
Go
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
|
package main
func countLargestGroup(n int) (ans int) {
times := map[int]int{}
maxTimes := 0
for i := 1; i <= n; i++ {
cnt := 0
for temp := i; temp > 0; temp /= 10 {
cnt += temp % 10
}
times[cnt]++
maxTimes = max(maxTimes, times[cnt])
}
for _, val := range times {
if val == maxTimes {
ans++
}
}
return
}
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源