力扣热题——统计最大组的数目
目录
题目链接:1399. 统计最大组的数目 - 力扣(LeetCode)
题目描述
解法一:哈希表
Java写法:
C++写法:
运行时间
时间复杂度和空间复杂度
时间复杂度
空间复杂度
题目链接:1399. 统计最大组的数目 - 力扣(LeetCode)
注:下述题目描述和示例均来自力扣
题目描述
给你一个整数 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 <=
解法一:哈希表
-
计算数位和:
- 对于一个整数
num
,可以通过不断地取模 (num % 10
) 和整除 (num /= 10
) 来提取每一位数字,并将其累加。
- 对于一个整数
-
使用哈希表存储分组信息:
- 使用一个数组或哈希表来记录每个数位和对应的数字数量。例如,
count[sum]
表示数位和为sum
的组中包含多少个数字。
- 使用一个数组或哈希表来记录每个数位和对应的数字数量。例如,
-
遍历所有数字:
- 遍历从
1
到n
的所有数字,计算它们的数位和,并更新对应的计数器。
- 遍历从
-
找出最大值及其次数:
- 遍历计数器数组,找到最大值(即最大的组大小),并统计有多少个组的大小等于这个最大值。
-
返回结果:
- 返回拥有最多数字的组的数量。
Java写法:
import java.util.HashMap;public class Solution {public int countLargestGroup(int n) {// 使用哈希表记录每个数位和对应的数字数量HashMap<Integer, Integer> sumCountMap = new HashMap<>();// 遍历从 1 到 n 的所有数字for (int i = 1; i <= n; i++) {// 计算当前数字的数位和int digitSum = getDigitSum(i);// 更新哈希表中对应数位和的计数sumCountMap.put(digitSum, sumCountMap.getOrDefault(digitSum, 0) + 1);}// 找出最大组的大小以及并列最多的组的数量int maxSize = 0; // 最大组的大小int maxCount = 0; // 并列最多的组的数量// 遍历哈希表中的所有值for (int count : sumCountMap.values()) {if (count > maxSize) {// 如果发现更大的组大小,更新最大值,并重置计数maxSize = count;maxCount = 1;} else if (count == maxSize) {// 如果组大小等于当前最大值,增加计数maxCount++;}}// 返回并列最多的组的数量return maxCount;}// 辅助方法:计算一个数字的数位和private int getDigitSum(int num) {int sum = 0;while (num > 0) {sum += num % 10; // 取出最后一位数字并累加num /= 10; // 去掉最后一位数字}return sum;}// 主方法用于测试public static void main(String[] args) {Solution solution = new Solution();int n = 13;System.out.println(solution.countLargestGroup(n)); // 输出: 4}
}
C++写法:
#include <iostream>
#include <unordered_map>
#include <algorithm>using namespace std;class Solution {
public:// 主函数:计算并列最多的组的数量int countLargestGroup(int n) {// 使用哈希表记录每个数位和对应的数字数量unordered_map<int, int> sumCountMap;// 遍历从 1 到 n 的所有数字for (int i = 1; i <= n; ++i) {// 计算当前数字的数位和int digitSum = getDigitSum(i);// 更新哈希表中对应数位和的计数sumCountMap[digitSum]++;}// 找出最大组的大小以及并列最多的组的数量int maxSize = 0; // 最大组的大小int maxCount = 0; // 并列最多的组的数量// 遍历哈希表中的所有值for (const auto& entry : sumCountMap) {int count = entry.second;if (count > maxSize) {// 如果发现更大的组大小,更新最大值,并重置计数maxSize = count;maxCount = 1;} else if (count == maxSize) {// 如果组大小等于当前最大值,增加计数maxCount++;}}// 返回并列最多的组的数量return maxCount;}private:// 辅助函数:计算一个数字的数位和int getDigitSum(int num) {int sum = 0;while (num > 0) {sum += num % 10; // 取出最后一位数字并累加num /= 10; // 去掉最后一位数字}return sum;}
};// 主函数用于测试
int main() {Solution solution;int n = 13;cout << solution.countLargestGroup(n) << endl; // 输出: 4return 0;
}
-
unordered_map
:- C++ 标准库中的哈希表实现,用于快速存储和查找键值对。
- 在这里用于记录每个数位和对应的数字数量。
-
auto
关键字:- 自动推导变量类型,简化代码书写。例如,
for (const auto& entry : sumCountMap)
中的entry
是一个键值对。
- 自动推导变量类型,简化代码书写。例如,
-
cout
和endl
:- C++ 标准输出流,用于打印结果。
endl
表示换行。
- C++ 标准输出流,用于打印结果。
运行时间
能过就行了呗
时间复杂度和空间复杂度
时间复杂度
-
计算数位和:
- 对于每一个数字
i
(从1
到n
),我们需要计算它的数位和。计算数位和的过程涉及到对i
的每一位进行处理,这个过程的时间复杂度是。因为整数
i
的位数大致与其大小成对数关系,具体来说,给出了数字
i
的位数。
- 对于每一个数字
-
遍历所有数字:
- 需要遍历从
1
到n
的所有数字,因此这部分操作的时间复杂度为O(n)
。
- 需要遍历从
-
综合考虑:
- 由于对于每个数字
i
,我们都需要进行的操作来计算数位和,所以总的时间复杂度为
。这里假设
对于所有的
i
平均情况下接近于log_{10}(n)
。
- 由于对于每个数字
-
查找最大组大小及其次数:
- 在最后一步中,我们需要遍历哈希表中的所有值来找出最大组大小以及并列最多的组的数量。在最坏情况下,这一步的操作次数与不同数位和的数量有关,但由于数位和的最大值受限于
(即最大的可能数位和),这部分可以视为常数操作相对于
n
来说。
- 在最后一步中,我们需要遍历哈希表中的所有值来找出最大组大小以及并列最多的组的数量。在最坏情况下,这一步的操作次数与不同数位和的数量有关,但由于数位和的最大值受限于
因此,整体时间复杂度主要由前两步决定,为 。
空间复杂度
- 存储数位和的计数器:
- 我们使用了一个哈希表(
unordered_map<int, int>
)来记录每个数位和对应的数字数量。理论上,不同的数位和的数量最多为9 * \lceil log_{10}(n) \rceil
,这是因为数位和取决于数字的位数及其各位上的最大值(9)。然而,在实际应用中,考虑到数位和的分布情况,哈希表的大小通常会小于这个理论上限。
- 我们使用了一个哈希表(
- 其他额外空间:
- 主要是用于函数调用和局部变量的空间,这些都可以视为常数级别的空间消耗
O(1)
。
- 主要是用于函数调用和局部变量的空间,这些都可以视为常数级别的空间消耗
综上所述,空间复杂度主要由哈希表决定,大致为 O(k)
,其中 k
是不同数位和的数量,而在最坏情况下,k
最大可达 9 * \lceil log_{10}(n) \rceil
,但在实际情况中往往会更小。
总结:
- 时间复杂度:
O(
)
- 空间复杂度:
O(k)
,其中表示不同数位和的数量。