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

2011-09-24

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

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

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

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 + 22*101

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

根据以上分析,可以得出:当前是第x+1位,数字是a,则1-a*10x(232中百位上是:1-200)中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):

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)。对于算法二,总结很重要。

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