英文网站标题字体,科技公司网站制作模板,一家专门做原型的网站,呼和浩特网络推广公司问题描述
小M和小F在玩飞行棋。游戏结束后#xff0c;他们需要将桌上的飞行棋棋子分组整理好。现在有 N 个棋子#xff0c;每个棋子上有一个数字序号。小M的目标是将这些棋子分成 M 组#xff0c;每组恰好5个#xff0c;并且组内棋子的序号相同。小M希望知道是否可以按照这…问题描述
小M和小F在玩飞行棋。游戏结束后他们需要将桌上的飞行棋棋子分组整理好。现在有 N 个棋子每个棋子上有一个数字序号。小M的目标是将这些棋子分成 M 组每组恰好5个并且组内棋子的序号相同。小M希望知道是否可以按照这种方式对棋子进行分组。
例如假设棋子序号为 [1, 2, 3, 4, 5]虽然只有5个棋子但由于序号不同因此不能形成有效的分组。如果序号是 [1, 1, 1, 1, 1, 2, 2, 2, 2, 2]则可以形成两个有效分组因此输出为 True。 测试样例
样例1 输入nums [1, 2, 3, 4, 5] 输出False 样例2 输入nums [1, 1, 1, 1, 2, 1, 2, 2, 2, 2] 输出True 样例3 输入nums [5, 5, 5, 5, 5, 5, 5, 5, 5, 5] 输出True 样例4 输入nums [7, 7, 7, 8, 8, 8, 8, 8, 7, 7] 输出True 样例5 输入nums [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9] 输出False 解决方案分析
出现次数计数首先我们需要统计每个数字的出现次数。检查能否分组对于每个数字的出现次数如果某个数字的出现次数不能被 5 整除则无法分成有效的组直接返回 False。判断是否可以分成 M 组如果所有数字的出现次数都能被 5 整除则返回 True表示可以按要求分组。
步骤
统计频率使用一个哈希表或字典来统计每个数字出现的次数。判断条件遍历统计的次数如果某个数字的出现次数不能被 5 整除直接返回 False。返回结果如果所有数字的出现次数都能被 5 整除返回 True。 代码实现 代码说明
unordered_map我们使用了 C 标准库中的 unordered_map 来存储每个数字及其出现的次数。它提供了快速的查找、插入和删除操作。循环遍历数字我们遍历 nums 数组将每个数字的出现次数统计到 count_map 中。检查条件遍历 count_map 中的每个数字和其对应的计数判断是否能被 5 整除。如果有任何数字的出现次数不能被 5 整除返回 False。最终返回如果所有数字的出现次数都能被 5 整除则返回 True。
测试用例解析
样例 1{1, 2, 3, 4, 5}每个数字出现一次无法分成组输出 False。样例 2{1, 1, 1, 1, 2, 1, 2, 2, 2, 2}1 的出现次数是 52 的出现次数是 5能分成 2 组输出 True。样例 3{5, 5, 5, 5, 5, 5, 5, 5, 5, 5}每个数字 5 出现 10 次能分成 2 组输出 True。样例 4{7, 7, 7, 8, 8, 8, 8, 8, 7, 7}7 和 8 都出现了 5 次能分成 2 组输出 True。样例 5{9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9}数字 9 出现了 11 次不能被 5 整除输出 False。
时间复杂度
统计数字频率需要遍历一次数组时间复杂度为 O(N)其中 N 是数组的长度。遍历哈希表的键值对最多需要 O(K) 的时间其中 K 是不同数字的个数在最坏情况下 K N。总体时间复杂度为 O(N)空间复杂度为 O(K)。
哈哈--
