剑指offer-31、整数中1出现的次数
<h2 id="题描述">题⽬描述</h2><p>求出 1~13 的整数中1出现的次数，并算出 100~1300 的整数中 1 出现的次数？为此他特别数了⼀下 1~13 中包含 1 的数字有 1、10、11、12、13 因此共出现 6 次，但是对于后⾯问题他就没辙了。 ACMer 希望你们帮帮他，并把问题更加普遍化，可以很快的求出任意⾮负整数区间中 1 出现的次数（从 1 到 n 中 1 出现的次数）。</p>
<p>输入：13</p>
<p>输出：6</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="暴力循环法">暴力循环法</h3>
<pre><code class="language-java">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) { // 检查当前位是否为1
count++;
}
num /= 10; // 移除最后一位
}
}
return count;
}
}
</code></pre>
<p>这道题如果使⽤暴⼒破解，肯定是会超时的，所以我们需要看看这⾥⾯有没有啥规律。</p>
<h3 id="递归法">递归法</h3>
<p>递归法通过将数字按位拆分来解决问题。以数字 21345 为例，可以将其分为 1-1345 和 1346-21345 两部分。1346-21345 中 1 的出现次数可以分为两种情况</p>
<ol>
<li><strong>1 出现在最高位 (万位)</strong>：
<ul>
<li>如果最高位大于 1（如此处的 2），则万位出现 1 的次数为 10000 次（10000-19999）。</li>
<li>如果最高位等于 1，则万位出现 1 的次数为 <code>(除去最高位后的数字 + 1)</code>次。</li>
</ul>
</li>
<li><strong>1 出现在其他位（千位、百位、十位、个位）</strong>：最高位数字 * (总位数 - 1) * 10^(剩余位数 - 1)。对于 21345，其他位出现 1 的次数为 <code>2 * 4 * 1000 = 8000</code>。然后再递归地计算 1-1345 中 1 出现的次数</li>
</ol>
<pre><code class="language-java">public class Solution {
public int countDigitOne(int n) {
if (n <= 0) return 0;
if (n < 10) return 1; // 1-9只有1个1
String 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;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(log n)。递归深度与数字 n 的位数 log₁₀(n) 成正比。</li>
<li><strong>空间复杂度</strong>：O(log n)。递归调用栈的深度。</li>
</ul>
<h3 id="按位统计法">按位统计法</h3>
<p>这是通过数学推导直接计算每一位上 1 出现的次数，然后求和。</p>
<p>对于每一位（个位、十位、百位...），我们可以将数字 n 划分为三部分：</p>
<ul>
<li><strong>高位 (high)</strong>：当前位左边的数字</li>
<li><strong>当前位 (cur)</strong>：正在考察的位上的数字</li>
<li><strong>低位 (low)</strong>：当前位右边的数字</li>
<li><strong>位因子 (digit)</strong>：表示当前位的权重（如个位是1，十位是10，百位是100）</li>
</ul>
<p>根据当前位 <code>cur</code>的值，1 的出现次数有以下三种情况：</p>
<ol>
<li><strong>cur == 0</strong>：当前位为 0 时，此位出现 1 的次数由高位决定，计算公式为 <code>high * digit</code>。<br>
例如，n=2304，求十位（digit=10）上1的出现次数。高位 high=23，当前位 cur=0，低位 low=4。十位为1的数字范围是0010-2219，看高位和低位相当于000-229，共230个数，即 23 * 10 = 230。</li>
<li><strong>cur == 1</strong>：当前位为 1 时，此位出现 1 的次数由高位和低位共同决定，计算公式为 <code>high * digit + low + 1</code>。<br>
例如，n=2314，求十位上1的出现次数。高位 high=23，当前位 cur=1，低位 low=4。十位为1的数字范围是0010-2314，看高位和低位相当于000-234，共235个数，即 23 * 10 + 4 + 1 = 235。</li>
<li><strong>cur > 1</strong>：当前位大于 1 时，此位出现 1 的次数由高位决定，计算公式为 <code>(high + 1) * digit</code>。<br>
例如，n=2324，求十位上1的出现次数。高位 high=23，当前位 cur=2，低位 low=4。十位为1的数字范围是0010-2319，看高位和低位相当于000-239，共240个数，即 (23 + 1) * 10 = 240。</li>
</ol>
<pre><code class="language-java">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;
}
}
</code></pre>
<ul>
<li>时间复杂度 O(log n) ： 循环数字 n 的位数，相当于使⽤了 log(n)，时间复杂度为 O(log n)</li>
<li>空间复杂度 O(1)：</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19089339
頁:
[1]