当前位置: 首页 > ai >正文

力扣热题——统计最大组的数目

目录

题目链接: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 <= 10^4

解法一:哈希表

  1. 计算数位和

    • 对于一个整数 num,可以通过不断地取模 (num % 10) 和整除 (num /= 10) 来提取每一位数字,并将其累加。
  2. 使用哈希表存储分组信息

    • 使用一个数组或哈希表来记录每个数位和对应的数字数量。例如,count[sum] 表示数位和为 sum 的组中包含多少个数字。
  3. 遍历所有数字

    • 遍历从 1 到 n 的所有数字,计算它们的数位和,并更新对应的计数器。
  4. 找出最大值及其次数

    • 遍历计数器数组,找到最大值(即最大的组大小),并统计有多少个组的大小等于这个最大值。
  5. 返回结果

    • 返回拥有最多数字的组的数量。

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;
}
  1. unordered_map

    • C++ 标准库中的哈希表实现,用于快速存储和查找键值对。
    • 在这里用于记录每个数位和对应的数字数量。
  2. auto 关键字

    • 自动推导变量类型,简化代码书写。例如,for (const auto& entry : sumCountMap) 中的 entry 是一个键值对。
  3. coutendl

    • C++ 标准输出流,用于打印结果。endl 表示换行。

 


运行时间

能过就行了呗

时间复杂度和空间复杂度

时间复杂度

  1. 计算数位和

    • 对于每一个数字 i(从 1 到 n),我们需要计算它的数位和。计算数位和的过程涉及到对 i 的每一位进行处理,这个过程的时间复杂度是 O(log_{10}(i))。因为整数 i 的位数大致与其大小成对数关系,具体来说,log_{10}(i) 给出了数字 i 的位数。
  2. 遍历所有数字

    • 需要遍历从 1 到 n 的所有数字,因此这部分操作的时间复杂度为 O(n)
  3. 综合考虑

    • 由于对于每个数字 i,我们都需要进行 O(log_{10}(i)) 的操作来计算数位和,所以总的时间复杂度为 O(n * log_{10}(n))。这里假设log_{10}(i) 对于所有的 i 平均情况下接近于 log_{10}(n)
  4. 查找最大组大小及其次数

    • 在最后一步中,我们需要遍历哈希表中的所有值来找出最大组大小以及并列最多的组的数量。在最坏情况下,这一步的操作次数与不同数位和的数量有关,但由于数位和的最大值受限于 9 * \lceil log_{10}(n) \rceil(即最大的可能数位和),这部分可以视为常数操作相对于 n 来说。

因此,整体时间复杂度主要由前两步决定,为 O(n * log_{10}(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(n * log_{10}(n))
  • 空间复杂度:O(k),其中 k <= 9 * \lceil log_{10}(n) \rceil 表示不同数位和的数量。

http://www.xdnf.cn/news/2014.html

相关文章:

  • 黑马Redis(三)黑马点评项目
  • 【昇腾】【训练】800TA2-910B使用LLaMA-Factory训练Qwen
  • 系统架构师2025年论文《微服务架构3》
  • 软件开发管理制度,项目研发制度,项目管理制度
  • 解决Spring Boot多模块自动配置失效问题
  • 如何把两个视频合并成一个视频?无需视频编辑器即可搞定视频合并
  • 【Java面试笔记:进阶】19.Java并发包提供了哪些并发工具类?
  • linux基础操作1------(文件命令)
  • STM32系列官方标准固件库的完整下载流程
  • MySql 数据 结构 转为SqlServer (简单)
  • WSL2-自定义安装
  • LLM数学推导——Transformer问题集——注意力机制——稀疏/高效注意力
  • Kafka与Spark-Streaming
  • 7.0 sharpScada的sql数据的安装
  • Oracle Recovery Tools修复ORA-00742、ORA-600 ktbair2: illegal inheritance故障
  • ubuntu使用dify源码安装部署教程+避坑指南
  • 系统架构-安全架构设计
  • PS读写BRAM
  • 【从零开始:自制一个Java消息队列(MQ)】
  • Ubuntu18.04更改时区(图文详解)
  • 二叉树的遍历(深度优先搜索)
  • 如何确保微型导轨的质量稳定?
  • 【FAS】《Face Detection Algorithm Based on Lightweight Network and Near Infrared》
  • 张 LLM提示词拓展16中方式
  • 安卓 Compose 相对传统 View 的优势
  • Python常见报错及解决方法,包含示例代码
  • 20250418-vue-作用域插槽
  • MySQL 详解之备份与恢复策略:数据安全的最后一道防线
  • BT151-ASEMI无人机专用功率器件BT151
  • 软件测试入门学习笔记