当前位置：首页 > news >正文

剑指offer-31、整数中1出现的次数

news 2025/9/18 9:01:33

题⽬描述

求出 1~13 的整数中1出现的次数，并算出 100~1300 的整数中 1 出现的次数？为此他特别数了⼀下 1~13 中包含 1 的数字有 1、10、11、12、13 因此共出现 6 次，但是对于后⾯问题他就没辙了。 ACMer 希望你们帮帮他，并把问题更加普遍化，可以很快的求出任意⾮负整数区间中 1 出现的次数（从 1 到 n 中 1 出现的次数）。

输入：13

输出：6

思路及解答

暴力循环法

public class Solution {public int countDigitOne(int n) {if (n <= 0) {return 0;}int count = 0;for (int i = 1; i <= n; i++) {int num = i;while (num > 0) {if (num % 10 == 1) { // 检查当前位是否为1count++;}num /= 10; // 移除最后一位}}return count;}
}

这道题如果使⽤暴⼒破解，肯定是会超时的，所以我们需要看看这⾥⾯有没有啥规律。

递归法

递归法通过将数字按位拆分来解决问题。以数字 21345 为例，可以将其分为 1-1345 和 1346-21345 两部分。1346-21345 中 1 的出现次数可以分为两种情况

1 出现在最高位 (万位)：
- 如果最高位大于 1（如此处的 2），则万位出现 1 的次数为 10000 次（10000-19999）。
- 如果最高位等于 1，则万位出现 1 的次数为 (除去最高位后的数字 + 1)次。
1 出现在其他位（千位、百位、十位、个位）：最高位数字 * (总位数 - 1) * 10^(剩余位数 - 1)。对于 21345，其他位出现 1 的次数为 2 * 4 * 1000 = 8000。然后再递归地计算 1-1345 中 1 出现的次数

public class Solution {public int countDigitOne(int n) {if (n <= 0) return 0;if (n < 10) return 1; // 1-9只有1个1String str = String.valueOf(n);int len = str.length();int firstDigit = str.charAt(0) - '0'; // 获取首位数字int remainder = n % (int)Math.pow(10, len - 1); // 获取除首位后的余数int power = (int)Math.pow(10, len - 2); // 用于计算其他位出现1的次数int countFirstDigit = 0;// 计算最高位出现1的次数if (firstDigit > 1) {countFirstDigit = (int)Math.pow(10, len - 1);} else if (firstDigit == 1) {countFirstDigit = remainder + 1;}// 计算其他位出现1的次数int countOtherDigits = firstDigit * (len - 1) * (int)Math.pow(10, len - 2);// 递归计算剩余部分(1到 remainder)中1出现的次数int countRemainder = countDigitOne(remainder);return countFirstDigit + countOtherDigits + countRemainder;}
}

时间复杂度：O(log n)。递归深度与数字 n 的位数 log₁₀(n) 成正比。
空间复杂度：O(log n)。递归调用栈的深度。

按位统计法

这是通过数学推导直接计算每一位上 1 出现的次数，然后求和。

对于每一位（个位、十位、百位...），我们可以将数字 n 划分为三部分：

高位 (high)：当前位左边的数字
当前位 (cur)：正在考察的位上的数字
低位 (low)：当前位右边的数字
位因子 (digit)：表示当前位的权重（如个位是1，十位是10，百位是100）

根据当前位 cur的值，1 的出现次数有以下三种情况：

cur == 0：当前位为 0 时，此位出现 1 的次数由高位决定，计算公式为 high * digit。
例如，n=2304，求十位（digit=10）上1的出现次数。高位 high=23，当前位 cur=0，低位 low=4。十位为1的数字范围是0010-2219，看高位和低位相当于000-229，共230个数，即 23 * 10 = 230。
cur == 1：当前位为 1 时，此位出现 1 的次数由高位和低位共同决定，计算公式为 high * digit + low + 1。
例如，n=2314，求十位上1的出现次数。高位 high=23，当前位 cur=1，低位 low=4。十位为1的数字范围是0010-2314，看高位和低位相当于000-234，共235个数，即 23 * 10 + 4 + 1 = 235。
cur > 1：当前位大于 1 时，此位出现 1 的次数由高位决定，计算公式为 (high + 1) * digit。
例如，n=2324，求十位上1的出现次数。高位 high=23，当前位 cur=2，低位 low=4。十位为1的数字范围是0010-2319，看高位和低位相当于000-239，共240个数，即 (23 + 1) * 10 = 240。

public class Solution {public int countDigitOne(int n) {if (n <= 0) return 0;int count = 0;long digit = 1; // 位因子，从个位开始int high = n / 10; // 高位int cur = n % 10; // 当前位int low = 0; // 低位while (high != 0 || cur != 0) {if (cur == 0) {count += high * digit;} else if (cur == 1) {count += high * digit + low + 1;} else {count += (high + 1) * digit;}// 更新低位、当前位、高位和位因子low += cur * digit;cur = high % 10;high = high / 10;digit *= 10;}return count;}
}