MediumRating 1734
2048. Next Greater Numerically Balanced Number
hash-tablemathbacktrackingcountingenumeration
解題說明
Next Greater Numerically Balanced Number
題目描述: 一個數字是「數值平衡」的,如果每個出現的數字 d 恰好出現 d 次。例如 1210 不是(0 出現了 1 次但不是 0 次),而 1224444 是(1 出現 1 次、2 出現 2 次、4 出現 4 次)。給定整數 n,找到大於 n 的最小數值平衡數。
解題思路: 由於 n 最大為 10^6,答案最多為 7 位數。數值平衡數的數量非常有限,最直接的方法是逐一檢查 n+1, n+2, ... 直到找到一個數值平衡數。
判斷一個數是否為數值平衡數:統計每個數字出現的次數,檢查每個出現過的數字 d 是否恰好出現 d 次,且未出現的數字出現次數為 0。
n 最大為 10^6,而下一個數值平衡數不會離 n 太遠(最多幾千步),因此暴力枚舉足夠高效。
C++ 解法
複雜度分析
時間複雜度:O(G * D) — G 為從 n+1 到下一個平衡數的距離(實測最多不超過幾千),D 為數字的位數(最多 7 位)。整體而言非常快速。
空間複雜度:O(1) — 僅使用固定大小的計數陣列。
虛擬碼
1. Define IS_BALANCED(num): a. Count occurrences of each digit 0-9. b. For each digit d with count > 0, check if count == d. c. Return true if all checks pass. 2. For x = n+1, n+2, ...: a. If IS_BALANCED(x), return x.
其他解法
-
預計算所有平衡數:由於 7 位數以內的數值平衡數非常少(約一百多個),可以用回溯法枚舉所有可能的組合(如 1 個 1、2 個 2、3 個 3 等),生成所有排列,排序後用二分搜尋找到大於 n 的最小值。預處理 O(C) 後查詢 O(log C),C 為平衡數總數。
-
組合數學構造法:先確定位數 k,然後將 k 分配給各個數字(如 k=4 可以分為 1+3 或 4 或 2+2 或 1+1+2),再用排列組合生成所有可能的數字。這避免了逐一枚舉,但實作較複雜。
延伸思考
- 如果 n 可以到 10^18,暴力枚舉不再可行,如何用組合構造法直接找到答案?
- 能否在 O(1) 或 O(log n) 時間內判斷一個範圍 [a, b] 中有多少個數值平衡數?
- 若將「數字 d 出現 d 次」改為「數字 d 出現 d+1 次」,平衡數的分布會如何變化?