求给定数中每位数字出现频率最接近的2的幂次方
本文描述了一种计算给定数中每位数字出现频率最接近的2的幂次方的方法。"频率"指的是该数中每个不同数字出现的次数。
问题描述
求正整数 N 中每位数字出现的次数。然后，对于每位数字，找出与其频率最接近的2的幂次方。如果任意频率有两个最接近的 2 的幂，则打印较大的那个。
示例
输入
n = 677755
输出
5 -> 2 6 -> 1 7 -> 4
解释
对于 n = 677755，每个数字的频率为:
数字 5:2
数字 6:1
数字 7:3
与这些频率最接近的 2 的幂是:
数字 5:2
数字 6:1
数字 7:4
输入
n = 9990110466996
输出
1 -> 2 0 -> 2 4 -> 1 6 -> 4 9 -> 8
解释
对于 n = 9990110466996，每个数字的频率为:
数字 6:3
数字 9:5
数字 4:1
数字 0:2
数字 1:2
最接近这些频率的 2 的幂为:
数字 0:2
数字 1:2
数字 4:1
数字 6:4
数字 9:8
解决方法
此任务的一个可行策略是利用 map 数据结构来存储给定数字中每个数字的出现频率，然后将其调整为最接近的相等值或更大的2的幂次方。
伪代码
启动程序。
声明一个 long long int 类型的变量 `n` 并初始化它。
创建一个空的 unordered_map `freq` 来存储每个数字的频率。
通过执行以下步骤迭代 `n` 的每个数字，直到 `n` 变为零:
通过计算 `n % 10` 获取 `n` 的最后一位数字。
使用 `freq[digit]++` 增加 `freq` 映射中该数字的频率。
通过将 `n` 除以 10 来删除其最后一位数字(`n /= 10`)。
按照以下步骤迭代 `freq` 映射中的键值对:
对于每一对，声明一个整数变量 `power` 并将其设置为 1。
迭代 2 的幂，直到遇到大于或等于相应频率值 (it.second) 的幂:
将 `power` 乘以 2 (`power *= 2`)。
打印数字 (`it.first`) 和最接近的 2 的幂 (`power`)。
结束程序。
示例:C++ 程序
在下面的 C++ 程序中，我们输出最接近的给定数字中每个不同数字出现频率的2的幂次方。我们使用频率图来存储每个数字的实际出现次数，然后使用while循环将频率调整到最接近的2的幂次方。
示例
// 以下 C++ 程序返回 N 中每个数字出现频率最接近的2的幂次方。
#include <iostream>
#include <unordered_map>
#include <cmath>
using namespace std;
int main() {
long long int n;
n = 9990110466996;
// 声明一个映射表来跟踪每个数字的频率。
unordered_map<int, int> freq;
// 迭代输入数字并增加每个数字的频率。
while (n) {
freq[n % 10]++;
n /= 10;
}
// 迭代映射表并打印每个频率最接近的2的幂。
for (auto it : freq) {
// 声明一个变量来存储最接近的2的幂。
int power = 1;
// 迭代2的幂，直到找到大于或等于频率的幂。
while (power < it.second) {
power *= 2;
}
// 打印数字及其最接近的 2 的幂。
cout << it.first << " -> " << power << endl;
}
return 0;
}
输出
1 -> 2 0 -> 2 4 -> 1 6 -> 4 9 -> 8
时间和空间复杂度分析
时间复杂度:O(log n)
迭代输入数字并递增每位数字的频率需要 O(log n) 时间，其中 n 表示输入数字。这是因为数字 n 中的位数与 log n 成正比。
迭代映射并打印每个频率最接近的 2 的幂需要 O(k) 时间，其中 k 表示输入数字中唯一数字的位数。在最坏情况下，k 可以视为常数。
空间复杂度:O(k)
创建一个无序映射来存储数字中每位数字的频率，其空间复杂度与该数字中唯一数字的位数成正比。在最坏情况下，空间复杂度为常数。
结论
本文提出了一种确定给定数字中每个数字出现频率最接近的2的幂次方的方法。该解决方案使用一个映射数据结构来存储给定数字中每个数字的出现频率，然后将其调整为最接近的等于或大于2的幂次方的值。
该解决方案的时间复杂度为 O(log n)，空间复杂度为 O(k)，其中 n 是输入数字的值，k 是输入数字中唯一数字的数量。实现此方法相对简单。
