[LeetCode] 每日一题 1399. 统计最大组的数目（暴力求解）

题目描述

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

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

题目链接

https://leetcode.cn/problems/count-largest-group

示例输入

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

提示

• 1 <= n <= 10^4

解题思路

这题的本质是一个分组统计问题，题目要求我们将 1 到 n 中每个数按数位和进行分组，然后返回数目最多的组的个数。

这类题没有太复杂的算法成分，但需要注意两个点：

1. 如何高效计算数位和：我们可以用 O(log n) 的方法将一个数不断除以 10，依次取每一位数字相加。

2. 如何进行计数和最大值更新：使用一个一维数组进行映射存储数位和的出现次数，这样可以避免 HashMap 在 Java 中动态扩容所带来的性能波动，也能让整体代码更紧凑高效。

我们维护一个 max 来记录当前最大的分组大小，以及 ans 表示有多少个组的大小达到了这个最大值。

这道题虽然标签是“暴力”，但整体实现仍然可以做到非常高效！

代码实现

class Solution {
    public int countLargestGroup(int n) {
        int len = String.valueOf(n).length();
        int[] count = new int[len * 9 + 1];
        int max = -1;
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int digitSum = calculate(i);
            count[digitSum]++;
            if (count[digitSum] == max) {
                ans++;
            } else if (count[digitSum] > max) {
                max = count[digitSum];
                ans = 1;
            }
        }
        return ans;
    }

    private int calculate(int n) {
        int res = 0;
        while (n > 0) {
            res += n % 10;
            n /= 10;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n log n) ⏱️
  每个数字都需要计算一次数位和，最多 log₁₀(n) 次除法操作

• 空间复杂度：O(1) 📦
  虽然我们用了一个数组，但长度固定为 len * 9 + 1，和输入规模无关

总结

这题虽然思路直接，但细节处理还是有优化空间的。比如使用数组代替哈希表提升性能，统计过程中动态更新最大值和结果个数等。对于这种计数类题目，空间换时间是非常常见的技巧！💡

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。