给定数字的每个数字频率的最近的 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

解决方案方法

此任务的一种可行的策略包括利用映射数据结构来存储给定数字中每个数字出现的频率，然后将其调整为最近的等于或大于 2 的幂。

伪代码

• 启动程序。

• 声明一个名为 `n` 的 `long long int` 类型的变量并进行初始化。

• 创建一个空的无序映射 `freq` 来存储每个数字的频率。

• 通过执行以下步骤迭代 `n` 的数字，直到 `n` 变为零

• 通过计算 `n % 10` 获取 `n` 的最后一位数字。

• 使用 `freq[digit]++` 将该数字在 `freq` 映射中的频率递增。

• 通过将其除以 10 (`n /= 10`) 从 `n` 中移除最后一位数字。

• 通过执行以下步骤迭代 `freq` 映射中的键值对

• 对于每一对，声明一个整数变量 `power` 并将其设置为 1。

• 遍历 2 的幂，直到遇到一个大于或等于对应频率值 (it.second) 的幂

• 将 `power` 乘以 2 (`power *= 2`)。

• 打印数字 (`it.first`) 和最近的 2 的幂 (`power`)。

• 结束程序。

示例：C++ 程序

在下面的 C++ 程序中，我们输出给定数字中每个唯一数字频率的最近的 2 的幂。我们使用频率映射来存储每个数字的实际出现次数，然后使用 while 循环将频率调整为最近的 2 的幂。

示例

// The following C++ program returns the closest power of 2 of the frequencies of each digit present in N.

#include <iostream>
#include <unordered_map>
#include <cmath>
using namespace std;

int main() {
  long long int n;
  n = 9990110466996;
// Declare a map to keep track of the frequency of each digit.
  unordered_map<int, int> freq;
  // Iterate over the input number and increment the frequency of each digit.
  while (n) {
   freq[n % 10]++;
   n /= 10;
  }
  // Iterate over the map and print the nearest power of 2 for each frequency.
  for (auto it : freq) {
   // Declare a variable to store the nearest power of 2.
   int power = 1;
   // Iterate over the powers of 2 until we find a power that is greater than or equal to the frequency.
   while (power < it.second) {
      power *= 2;
   }
   // Print the digit and the nearest power of 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 是输入数字中唯一数字的数量。实现此方法相对简单。