文章目錄
- 題目
- 思路
- 代碼
- 復雜度分析
題目
輸入一個整數 n ，求1～n這n個整數的十進制表示中1出現的次數。
例如，輸入12，那么1～12這些整數中包含1 的數字有1、10、11和12。可得1一共出現了5次。
思路
將個位、十位……每位1出現的次數加起來就是1一共出現的次數。
以12為例，個位上1出現了 2 次分別是 01，11（暫時不看11的十位）。
十位上1出現了 3 次，分別是10，11，12。
因此1~12中1一共出現了 2+3=5 次。
兩位數不好找規律，我們以四位數為例。一個四位數十位上 1 出現的次數，與十位上的值有關。根據值不同，可分為三種情況，值為0，1，2~9：
我們通過三個不同四位數進行探討，分別是 2304 ， 2314 和 2324 ：
我們將數字劃分為三部分，當前位（cur），高位（high），以及低位（low），用digit表示當前處于哪個數位。
- 當
cur = 0時： 此位 1 的出現次數只由高位high決定，計算公式為：
high×digit
詳細分析：
對于2304來講，十位出現1的范圍：0010~2219 沒有什么可多說的。
那么1出現的次數怎么算呢？
光看高位的話，00 ~ 22 總共有 23 種數字，也就是 001X ~ 221X 。而其中的 ‘X'，有 0 ~ 9 總共 10 種取法，也就是說排列組合下來，可以構成有 23*10=230 個十位為1的數字，如下表：
| high | cur | low |
|---|---|---|
| 00 | 1 | 0 |
| 00 | 1 | 1 |
| 00 | 1 | 2 |
| 00 | 1 | 3 |
| 00 | 1 | 4 |
| 00 | 1 | 5 |
| 00 | 1 | 6 |
| 00 | 1 | 7 |
| 00 | 1 | 8 |
| 00 | 1 | 9 |
| … | 1 | … |
| 22 | 1 | 0 |
| 22 | 1 | 1 |
| 22 | 1 | 2 |
| 22 | 1 | 3 |
| 22 | 1 | 4 |
| 22 | 1 | 5 |
| 22 | 1 | 6 |
| 22 | 1 | 7 |
| 22 | 1 | 8 |
| 22 | 1 | 9 |
- 當
cur = 1時： 此位 1 的出現次數由高位high和低位low共同決定，計算公式為：
high×digit+low+1
詳細分析：
十位上1出現的次數怎么算呢？
出現 1 的數字范圍： 0010 ~ 2314
光看高位的話，有 00 ~ 23 總共 24 種組合排列方法，但是！ 對于 00 ~ 22 這 23 種高位來講，低位都有 0 ~ 9 總共 10 種排列組合 —— 0010 ~ 0019 或 2210 ~ 2219 ，但是 23 不同，其低位只有 0 ~ 4 五種排列組合 —— 2310 ~ 2314 。因此，可以構成 23*10+5=235 個十位為 1 的數字（23*10代表 【高位為00~22】 的所有數字，5代表 【高位為23】 的所有數字）。
- 當
cur=2,3,?,9時： 此位 1 的出現次數只由高位high決定，計算公式為：
(high+1)×digit
詳細分析：
十位上1出現的次數怎么算呢？
此時與 cur=1 不同，cur=1 時出現的次數還需要看 low 的值，此時出現 1 的數字范圍： 0010 ~ 2319 ，也就是說，高位為 23 時，低位也有 0 ~ 9 共計 10 種排列組合方法，與高位為 00 ~ 22 時一樣，因此，cur=2~9 時，十位上 1 出現的次數為：24*10=240 。
上面各圖源自jyd大佬
代碼
class Solution {
public:int countDigitOne(int n) {long long digit = 1;int low = 0;int cur = n % 10;int high = n / 10;int sum = 0;while(high || cur){if(cur==0){sum += high * digit;}if(cur==1){sum += high*digit+low+1;}if(cur!=0 && cur!=1){sum += (high+1)*digit;}low += cur * digit;cur = high % 10;high /= 10;digit *= 10;}return sum;}
};
復雜度分析
時間復雜度 O(logn)： 循環內的計算操作使用 O(1) 時間；循環次數為數字 n 的位數，即 log10n，因此循環使用 O(logn) 時間。
空間復雜度 O(1) ： 幾個變量使用常數大小的額外空間。
