參考： https://troywu0.gitbooks.io/interview/整數中出現1的次數（從1到n整數中1出現的次數）.html
題目描述
求出1~13的整數中1出現的次數,并算出100~1300的整數中1出現的次數？為此他特別數了一下1~13中包含1的數字有1、10、11、12、13因此共出現6次,但是對于后面問題他就沒轍了，ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數（從1 到 n 中1出現的次數），解題思路1 （暴力法，時間復雜度: O(nlog(n)）
1 public int NumberOf1Between1AndN_Solution(int n) { 2 int count = 0; 3 while (n > 0) { 4 String nStr = String.valueOf(n); 5 for (int i = 0; i < nStr.length(); i++) { 6 if (nStr.charAt(i) == '1') 7 count++; 8 } 9 n--; 10 } 11 return count; 12 }
這種方法的思路簡單，統計每一個數中出現1的次數，能夠快速寫出代碼，但是，這種方法的時間復雜度很高，O(nlog(n))，面試這么寫，估計不會留下好的印象，
解題思路2 （數學規律法，時間復雜度: O(log(n)）
1 public int NumberOf1Between1AndN_Solution(int n) { 2 int low = 0, cur = 0, high = 0; 3 int count = 0; 4 int factor = 1; 5 while (factor <= n) { 6 high = n / (factor * 10); 7 low = n % factor; 8 // cur = (n - high * (factor * 10) - low) / factor; 9 cur = (n / factor) % 10; 10 if (cur == 0) 11 count += high * factor; 12 else if (cur == 1) 13 count += high * factor + low + 1; 14 else 15 count += (high + 1) * factor; 16 factor *= 10; 17 } 18 return count; 19 }
這一個思路利用了數字的規律和特點，解決問題的效率非常的高，時間復雜度只與數的位數有關，
首先看一個規律：
- 從1 - 10中，個位中 1 出現的次數是1，即1這個數；
- 從1 - 100中，十位中 1 出現的次數是10， 即10, 11, ..., 18, 19；
- 從1 - 1000中，百位中 1 出現的次數是100，即100, 101, ..., 198, 199；
- 以此類推，
假設有一個四位數，使用 cur 來表示當前位數對應的數值，high表述cur左邊的數，low表示cur右邊的數，會有三種情況產生：
- 第一種：cur = 0，1出現的次數等于 high * (該位數對應的基數)
- 假設四位數為1023，求百位上1出現的次數；
- 此時 high = 1, cur = 0, low = 23；
- 次數 = 1 * 100；
- 即100, 101, ..., 198, 199，
- 第二種：cur = 1，1出現的次數等于 high * (該位數對應的基數) + low + 1
- 假設四位數為1123，求百位上1出現的次數；
- 此時 high = 1, cur = 1, low = 23；
- 次數 = 1 * 100 + 23 + 1；
- 即100, 101, ..., 198, 199 + 1100, 1101, ..., 1122, 1123，
- 第三種：cur > 1，1出現的次數等于 (high + 1) * (該位數對應的基數)
- 假設四位數為1223，求百位上1出現的次數；
- 此時 high = 1, cur = 2, low = 23；
- 次數 = (1 + 1) * 100；
- 即100, 101, ..., 198, 199 + 1100, 1101, ..., 1198, 1199，
根據這一規律，從最低位至最高位，依次求出1出現的次數，最后相加得到最終的結果，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/116902.html
標籤：其他
下一篇：請教：關于TCP的快速重傳