1399-统计最大组的数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

给你一个整数 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 <= 10^4

方法一：哈希表

思路

对于 [1, n] 中的每一个整数 i，我们可以计算出它的数位和 s_i。建立一个从数位和到原数字的哈希映射，对每一个数字 i，使键 s_i 对应的值自增一。然后我们在值的集合中找到最大的值 m，再遍历哈希表，统计值为 m 的个数即可。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
class Solution:
    def countLargestGroup(self, n: int) -> int:
        hashMap = collections.Counter()
        for i in range(1, n + 1): 
            key = sum([int(x) for x in str(i)])
            hashMap[key] += 1
        maxValue = max(hashMap.values())
        count = sum(1 for v in hashMap.values() if v == maxValue)
        return count
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int countLargestGroup(int n) {
        unordered_map<int, int> hashMap;
        int maxValue = 0;
        for (int i = 1; i <= n; ++i) {
            int key = 0, i0 = i;
            while (i0) {
                key += i0 % 10;
                i0 /= 10;
            }
            ++hashMap[key];
            maxValue = max(maxValue, hashMap[key]);
        }
        int count = 0;
        for (auto& kvpair: hashMap) {
            if (kvpair.second == maxValue) {
                ++count;
            }
        }
        return count;
    }
};
[sol1-C++17]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int countLargestGroup(int n) {
        unordered_map<int, int> hashMap;
        int maxValue = 0;
        for (int i = 1; i <= n; ++i) {
            int key = 0, i0 = i;
            while (i0) {
                key += i0 % 10;
                i0 /= 10;
            }
            ++hashMap[key];
            maxValue = max(maxValue, hashMap[key]);
        }
        int count = 0;
        for (auto& [_, value]: hashMap) {
            if (value == maxValue) {
                ++count;
            }
        }
        return count;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int countLargestGroup(int n) {
        Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        int maxValue = 0;
        for (int i = 1; i <= n; ++i) {
            int key = 0, i0 = i;
            while (i0 != 0) {
                key += i0 % 10;
                i0 /= 10;
            }
            hashMap.put(key, hashMap.getOrDefault(key, 0) + 1);
            maxValue = Math.max(maxValue, hashMap.get(key));
        }
        int count = 0;
        for (Map.Entry<Integer, Integer> kvpair : hashMap.entrySet()) {
            if (kvpair.getValue() == maxValue) {
                ++count;
            }
        }
        return count;
    }
}

复杂度分析

  • 时间复杂度：对数 x 求数位和的时间为 O(\log_{10} x) = O(\log x)，因此总时间代价为 O(n \log n)，选出最大元素和遍历哈希表的时间代价均为 O(n)，故渐渐时间复杂度 O(n \log n) + O(n) = O(n \log n)。

  • 空间复杂度：使用哈希表作为辅助空间，n 的数位个数为 O(\log_{10} n) = O(\log n)，每一个数位都在 [0, 9] 之间，故哈希表最多包含的键的个数为 O(10 \log n) = O(\log n)，渐进空间复杂度为 O(\log n)。

 Comments
On this page
1399-统计最大组的数目