剑指Offer-整数中1出现的次数(从1到n整数中1出现的次数)

题目描述

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

解法

暴力法

思路：直接从1遍历到n，对每个数字判断含1的个数。这种方法效率实在是太差了，直接被舍弃🤒

时间复杂度为$O(n \times 10)$ Integer最大值为2147483647
空间复杂度为$O(1)$

叫不上名字法😂

从LeetCode大佬解法那里扒来的——面试题43. 1～n 整数中 1 出现的次数（清晰图解）

分别统计1-n中个位、十位、百位…1的个数并相加，则为1出现的总次数。

设数字$n$为$x$位数，并记$n$的第$i$位为$ni$，那么$n$可以表示为$n_nn{n-1}n{n-2}…n_in{i-1}…n_2n_1$

$n_i$为当前位，即为$cur$
$high$为当前位左边的数
$low$为当前位右边的数
$digit$为当前位的位因子，值为$10^i$

判断当前位上1的个数的方法是：

根据当前位$cur$值的不同，分为三种情况：

当前位$cur = 0$：1的个数只由$high$决定，计算公式为$high \times digit$

例如 $n = 2304$, 求十位的1的个数

当前位$cur = 0$：1的个数由$high\ and\ low$决定，计算公式为$high \times digit + low + 1$

例如 $n = 2314$, 求十位的1的个数

ps: 即相当于在情况1的基础上加上10、11、…、14的个数。

当前位$cur > 1$：1的个数由$high$决定，计算公式为$(high + 1) \times digit$

例如 $n = 2324$, 求十位的1的个数

ps: 即相当于在情况1的基础上加上10、11、…、19的个数。(正好为位因子的大小。)

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        if (n <= 0) return 0;
        // 初始化high, cur, low, digit
        int cur = n % 10;
        int low = 0;
        int high = n / 10;
        int digit = 1;
        // 记录个数
        int count = 0;
        // 当high和cur同时为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;
            // 构造下一轮的high, cur, low, digit
            low += cur * digit;
            digit *= 10;
            cur = high % 10;
            high = high / 10;
        }
        return count;
    }
}