统计数字——算法

题目

计算数字k在0到n中的出现的次数，k可能是0~9的一个值。

eg:例如n=12，k=1，在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]，我们发现1出现了5次 (1, 10, 11, 12)

思路

不知道大家对这个题的第一反应是什么，我对此的第一反应是

（1）

分解个位，十位，百位等各个位.通过不断的取模运算，将其拆分。然后累加所有的count之和就可得到结果。 const digitCounts = function (k, n) { let count=0； for(let i=0;i<=n;i++){ let j=i; //判断当前数是否单个数字 while(j>9){ if((j%10)===k){ count++; } j=parseInt(j/10); } if(j==k){ count++; } } return count; }

整个算法复杂度相当复杂，但是，智商有限啊啊，能做出来感觉就ok了。

（2）

最后在上看到有人用java写的一个算法，虽然复杂度也不低，但是目测实现起来也不是很难吧。 算法思路大体是：

将所有的n拼接成一个大的字符串。然后遍历字符串，将其与目标数k进行比对复杂度为n啊。 const digistCounts=function (k,n) { let count=0; let str=''; k=k+''; for(let i=0;i<=n;i++){ str+=i; } for(let j=0;j<str.length;j++){ if(str[j]===k){ count++; } } return count; };

就这样吧，感觉自己智商根本不在线。

参考算法1 参考算法2