作者:翟天保Steven 题目描述:输入一个整数 n ,求 1~n 这 n 个整数的十进制表示中 1 出现的次数 注意:11 这种情况算两次 数据范围:1≤n≤30000 进阶:空间复杂度O(1) ,时间复杂度O(logn) 示例:输入: 13 返回值: 6 解题思路:本题考察算法思维。两种解题思路: 1)按位统计法 将数字拆解,按位数统计1出现的次数。举例说明其中的规律。 假设数字有32134。 分析个位数出现1的次数:由3213个10和1个4组成,每个10里面就有1个1(只看个位),而4又大于1,所以还会出现1次个位为1的数字。 分析十位数出现1的次数:由321个100和1个34组成,每个100里面就有10个1(只看十位),从10到19,而34大于19,说明还会出现10次十位为1的数字。 分析百位数出现1的次数:由32个1000和1个134组成,每个1000里面就有100个1(只看百位),从100到199,而134小于199,说明还会出现35次百位为1的数字,即100到134。 基于上述规律列出每位数出现次数的公式:bitcount = n / (b * 10) * b + min(max(n % (b * 10)- b + 1, (long long)(0)), b)。 其中n为数字,b为当前位数,下面用百位数分析举例。n / (b * 10) 计算出当前位数高一级位的数量,*b表示对应1的数量,即有32个1000,32个1000就说明有32*100个1;max(n % (b * 10)- b + 1, (long long)(0))用来判断余出来的部分134是否大于100,如果换成一个小于100的数,那就取0,大于100的数就取超出100的部分,比如134就是100到134,共35个数;后面的min,是为了对超出100的部分做限制,假设134是234,那应该100到199最多100个数而不是235个数。 该算法时间复杂度为O(log10 n),与位数相关,常数级变量,本题的理想解法。 2)暴力循环 循环所有数字,对每个数字的所有位数也进行循环。该算法时间复杂度为O(nlog10 n)。 测试代码:1)按位统计法
2)暴力循环
|
|