剑指 Offer 43. 1～n 整数中 1 出现的次数

摘要

剑指 Offer 43. 1～n 整数中 1 出现的次数

一、数学思维解析

将1~ n的个位、十位、百位、...的1出现次数相加，即为1出现的总次数。

设数字n是个x位数，记n的第i位为ni​，则可将n写为 nxnx−1⋯n2n1：

• 称" ni" 为 当前位 ，记为 cur ，
• 将" ni−1ni−2⋯n2n1​ " 称为 低位 ，记为low ；
• 将" nxnx−1⋯ni+2ni+1​ " 称为高位 ，记为high 。
• 将10i称为位因子 ，记为digit。

某位中1出现次数的计算方法：根据当前位 cur值的不同，分为以下三种情况：

当 cur=0时： 此位1的出现次数只由高位 high决定，计算公式为：high×digit：

 当cur=1时： 此位1的出现次数由高位high和低位low决定，计算公式为：high×digit+low+1

当cur=2,3,⋯ ,9时： 此位1的出现次数只由高位 high决定，计算公式为：(high+1)×digit：

package Math;/*** @Classname JZ43整数中1出现的次数* @Description TODO* @Date 2023/3/7 20:55* @Created by xjl*/
public class JZ43整数中1出现的次数 {/*** @description 整数中1出现的次数 * @param: n* @date: 2023/3/7 20:56* @return: int* @author: xjl*/public int countDigitOne(int n) {int digit = 1, res = 0;int high = n / 10, cur = n % 10, low = 0;while (high != 0 || cur != 0) {if (cur == 0) {res += high * digit;} else if (cur == 1) {res += high * digit + low + 1;} else {res += (high + 1) * digit;}low += cur * digit;cur = high % 10;high /= 10;digit *= 10;}return res;}
}

复杂度分析：

• 时间复杂度O(log⁡n)： 循环内的计算操作使用O(1)时间；循环次数为数字n的位数，即log⁡10n，因此循环使用O(log⁡n)时间。
• 空间复杂度 O(1) ： 几个变量使用常数大小的额外空间。

二、暴力解析

一般是超时的选择

    /*** @description 相当于的暴力求解的顺序* @param: n* @date: 2023/3/7 21:15* @return: int* @author: xjl*/public int countDigitOne2(int n) {String result = "";for (int i = 1; i <= n; i++) {result += String.valueOf(i);}int count = 0;for (int i = 0; i < result.length(); i++) {if (result.charAt(i) == '1') {count++;}}return count;}

复杂度分析：

• 时间复杂度O(n)： 循环内的计算操作使用O(1)时间；循环次数为数字n的位数，即log⁡10n，因此循环使用O(log⁡n)时间。
• 空间复杂度 O(n) ： 几个变量使用常数大小的额外空间。

博文参考

《leetcode》