給定數字的每個數字頻率的最近的 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 是輸入數字中唯一數字的數量。實現此方法相對簡單。