Easy

题目描述

给你一个整数 n。

我们需要根据数字和来将 1 到 n 的数字进行分组。例如，数字 14 和 5 属于同一组，而 13 和 3 属于不同的组。

返回具有最大大小的组的数量，即元素数量最多的组有多少个。

示例 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]。

约束：

  • 1 <= n <= 10^4

提示：

  • 为范围内的每个整数计算数字和，找出最大的组。

解题思路

这道题的核心思路是通过哈希表统计每个数字和对应的数字个数，然后找出最大的组大小，最后统计有多少个组达到了这个最大大小。

解题步骤

  1. 计算数字和：对于每个数字 i（1 ≤ i ≤ n），计算其各位数字之和
  2. 分组统计：使用哈希表记录每个数字和对应的数字个数
  3. 找最大组：遍历哈希表，找出组的最大大小
  4. 统计数量：统计有多少个组达到了最大大小

时间复杂度优化

由于题目约束 n ≤ 10^4，最大的数字和不会超过 9×4 = 36（数字 9999），所以哈希表的大小是有限的。

计算数字和可以通过不断取模和除法来实现：

  • sum += num % 10 获取个位数
  • num /= 10 去掉个位数

这种方法简洁高效，时间复杂度为 O(n × log n)，其中 log n 是计算每个数字的位数所需的时间。

代码实现

class Solution {
public:
    int countLargestGroup(int n) {
        unordered_map<int, int> count;
        
        // 统计每个数字和的出现次数
        for (int i = 1; i <= n; i++) {
            int sum = 0;
            int num = i;
            while (num > 0) {
                sum += num % 10;
                num /= 10;
            }
            count[sum]++;
        }
        
        // 找到最大的组大小
        int maxSize = 0;
        for (auto& pair : count) {
            maxSize = max(maxSize, pair.second);
        }
        
        // 统计有多少个组达到最大大小
        int result = 0;
        for (auto& pair : count) {
            if (pair.second == maxSize) {
                result++;
            }
        }
        
        return result;
    }
};

class Solution:
    def countLargestGroup(self, n: int) -> int:
        count = {}
        
        # 统计每个数字和的出现次数
        for i in range(1, n + 1):
            digit_sum = 0
            num = i
            while num > 0:
                digit_sum += num % 10
                num //= 10
            count[digit_sum] = count.get(digit_sum, 0) + 1
        
        # 找到最大的组大小
        max_size = max(count.values())
        
        # 统计有多少个组达到最大大小
        return sum(1 for size in count.values() if size == max_size)

public class Solution {
    public int CountLargestGroup(int n) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        
        // 统计每个数字和的出现次数
        for (int i = 1; i <= n; i++) {
            int sum = 0;
            int num = i;
            while (num > 0) {
                sum += num % 10;
                num /= 10;
            }
            if (count.ContainsKey(sum)) {
                count[sum]++;
            } else {
                count[sum] = 1;
            }
        }
        
        // 找到最大的组大小
        int maxSize = 0;
        foreach (var pair in count) {
            maxSize = Math.Max(maxSize, pair.Value);
        }
        
        // 统计有多少个组达到最大大小
        int result = 0;
        foreach (var pair in count) {
            if (pair.Value == maxSize) {
                result++;
            }
        }
        
        return result;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var countLargestGroup = function(n) {
    const groups = new Map();
    
    for (let i = 1; i <= n; i++) {
        let sum = 0;
        let num = i;
        while (num > 0) {
            sum += num % 10;
            num = Math.floor(num / 10);
        }
        groups.set(sum, (groups.get(sum) || 0) + 1);
    }
    
    const maxSize = Math.max(...groups.values());
    return Array.from(groups.values()).filter(size => size === maxSize).length;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n × log n)需要遍历 1 到 n 的每个数字，计算每个数字的位数和需要 O(log n) 时间
空间复杂度O(1)哈希表最多存储 36 个不同的数字和（最大数字 9999 的数字和为 36），为常数空间