Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Example:
Input: 13 Output: 6 Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
分析¶
数字1的个数。最直接累加1到n中每个整数1出现的次数。可以每次通过对10求余数判断整数的个位数字是不是1。如果这个数字⼤于10,除以10之后再判断个位数字是不是1。如果输⼊数字n,n有O(logn)位,需要判断每⼀位是不是1,那么它的时间复杂度是O(nlog n).
public int countDigitOne(int n) { if (n <= 0) return 0; if (n < 10) return 1; int count = 0; for (int i = 10; i <= n; i++) count += numberOfOne(i); return count; } private int numberOfOne(int n) { int count = 0; while (n > 0) { if (n % 10 == 1) count++; n /= 10; } return count; }
但是过程中有非常多的重复计算,可以利用动态规划,如果把数字看作两部分:最高位和其他低位。那么1的个数是最高位中1的个数,然后加上保存下来的其他低位中的1的个数。
public int countDigitOne(int n) { if (n <= 0) return 0; if (n < 10) return 1; int[] countDigit = new int[n + 1]; countDigit[1] = 1; int base = 10; // 计算每个数中出现1的次数 for (int i = 10; i <= n; i++) { int highestDigit = i/base; if (highestDigit > 9) { base *= 10; highestDigit = i/base; } countDigit[ 大专栏 233. Number of Digit Onei] = (highestDigit == 1 ? 1: 0) + countDigit[i - highestDigit*base]; } // 累加1...n中的所有1 int count = 0; for (int i = 1; i <= n; i++) count += countDigit[i]; return count; }
以上两种算法的时间复杂度都是O(n),当n非常大时,程序运算将非常慢,而且动态规划需要O(n)的空间。
那么有没有更好的方法呢?假设5位数字21221,那么可以把该数字分割成以下几部分:
- 0~9999, 也就是4位数中出现1的总次数,那么0~20000要再乘以2
- 20000~21221中最高位中1出现的次数:出现10000次,即10000到19999
- 剩余的1221中1出现的次数:递归求解
那么怎么求解n位数中出现1的总次数呢?其实就是n-1位数中出现1的总次数,加上以1开头的n位数个数。
public int countDigitOne(int n) { if (n <= 0) return 0; if (n < 10) return 1; //计算n的位数 int number = n, numberOfDigits = 0; int highest = 0; // 最高位 while (number > 0) { highest = number; number/= 10; numberOfDigits++; } // lowerCount[i]为i位数字中出现1的所有数量 int[] lowerCount = new int[numberOfDigits]; lowerCount[1] = 1; int base = 10; for (int i = 2; i < numberOfDigits; i++) { lowerCount[i] = base + 10 * lowerCount[i - 1]; base *= 10; } int remaining = n - highest*base; int count = 0; // n = 259, remaining = 59 count = highest * lowerCount[numberOfDigits - 1] // i-1位数中出现的次数 + (highest == 1 ? n - base + 1: base) + // 最高位1重复出现的次数 + countDigitOne(remaining); // 除了最高位的次数 return count; }
⼀个数字n有O(log n)位,因此这种思路的时间复杂度是O(log n).