给定一个十进制整数N,求出从1到N的所有整数中出现1的个数

| |
| 966 | 4

今天下午去参加汇顶科技的一面，8个人群面，给了一道题，题目就是文章标题。一开始的时候要求大家用10分钟将自己的想法写在一张纸上面，到时间后就收上去了。然后让我们发表一下各自的思想，并讨论。讨论开始的时候大家意见都很统一，就是用遍历或者递归来解决，很简单的一道题。面试官马上看出了情况，就加上了个条件，不使用递归或者遍历数字来实现。

大家在短暂的思考后，就开始讨论了，各种各样的想法，有些都没听明白，我自己的思想也没表达太清楚，在那里的时候也没想得很透彻，基本上没有解决掉问题。马上面试就结束了。回来的路上也一直在想这个问题，回到寝室后开始在电脑上编码，两三下就实现了。唉，压力下思考不灵活啊！下面就说一下我的实现方法：

遍历数字实现
遍历数字实现很简单，只要写一个循环从1到N遍历，然后分析当前数字中有多少个1，并加起来就行了，用JavaScript实现的，因为电脑刚重装系统，没有C语言环境。代码如下：

1
2
3
4
5
6
7
8
9
10
11
function getOneCount(n) {
    var i, a, count = 0;
    for (i = 1; i <= n; i++) {
        a = i;
        while (a != 0) {
            if (a % 10 == 1) count++;
            a = parseInt(a / 10);
        }
    }
    return count;
}

上面的while循环就是分析每个数字中有多少个1，除10的余数，然后除10，直到变为0。我当时写的也是这个想法，不过不是写的代码。

探索规律实现
当时我的想法是：对于从1到N这N个数可以将其分解成：个位上共有多少个1，十位上共有多少个1……

然后对于给定的N，分析每一位上的数字，例如232可以分解成：1-200、1-30、1-2，这样1-2里面1的个数是1，1-30里面1的个数是101(十位) + 3 * 100(个位)，1-200里面1的个数是：102(百位) + 2 * 101(十位) + 20 * 100(个位)=102 + 2*2*101

对于上面的例子如果当前分析位上是1，同一位上1的个数应该是N除以10x(x是个位从0开始往前数)的余数+1，例如132就是32+1(100-132)。

根据以上分析，可以得出：当前是第x+1位，数字是a，则1-a*10x(232中百位上是：1-200)中1的个数如下：

1
count = (a == 1 ? (N % Math.pow(10,x) + 1) : Math.pow(10,x)) + a * x * Math.pow(10,x-1);

这里解释一下a * x * Math.pow(10,x-1);合并前是：a * 10x-1 + a * 101 * 10x-2 + …… + a * 10x-2101 + a * 10x-1 * 100 = a * x * 10x-1，其中每一项是a * 10x-1-i * 10i，表示分解后在1-a*10x中第i+1(右到左)位上是1的数字个数，其中a * 10x-1-i表示第i+1位的左边有多少种变化，10i表示第i+1位右边有多少种变化。相乘就是总共的变化数，即在1-a*10x区间，第i+1位是1的数字个数。

思想就讲到这里，不知道我表达清楚了没有。下面是实现代码(JavaScript)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function getOneCount(n) {
    var x = 0,
        a, t, count = 0;
    t = n;
    while (t != 0) {
        a = t % 10;
        if (a > 1) {
            count += Math.pow(10, x);
        } else if (a == 1) {
            count += n % Math.pow(10, x) + 1;
        }
        count += a * x * Math.pow(10, x - 1);
        t = parseInt(t / 10);
        x++;
    }
    return count;
}

总结
对于解法一的时间复杂度是O(N × lgN)，解法二的时间复杂度是O(lgN)。对于算法二，总结很重要。

大家还有什么其他更好的算法的话，欢迎留言！