1 1～n 整数中 1 出现的次数

问题描述

  • 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

链接

问题分析

问题分类

  • 数值问题

策略选择

算法设计

算法分析

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

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int countDigitOne(int n) {
    int i=0;
    int wei=0;
    int result=0;
    int end=0;
    while(n!=0){
        wei=n%10;
        i++;
        if(wei>1){
            result+=(i-1)*wei*pow(10,i-2)+pow(10,i-1);
        }
        else if(wei==1){
            result+=(i-1)*wei*pow(10,i-2)+end+1;
        }
        end+=wei*pow(10,i-1);
        // cout<<end<<endl;
        n/=10;
    }
    return result;
}