长春工业大学  Java 小组的一个笔试题

java笔试第4题,1~60000有多少个1，查出1~60000有多少个1

答案应该是34000

请编写一个程序,数出 1~60000 一共有多少个 1? 例如:1.2.3.4.5.6.7.8.9 中有 1 个 110.11.12.13.14.15.16.17.18.19 共有 11 个 1 所以1~20一共12个1.

暂时有2个思路，一个是比较 容易想到的方法：

方法一：

那就 是从 1 开始遍历到 N,将其中每一个数中含有“1”的个数加起来, 自然就得到了从 1 到 N 所有“1”的个数的和。写成程序如下:

public static int countOneByOne( int num){
    int count = 0;

    for(int i = 0;i <= num; i++){

        int tmp = i;
        while(tmp != 0){
            if(tmp % 10 == 1)
            count++;
        tmp/=10;

        }
    }
    return count;
}

但是这个算法的致命问题是效率,它的 时间复杂度是

O(N)×计算一个整数数字里面“1”的个数的复杂度 = O(N * log2 N)

如果给定的 N 比较大,则需要很长的运算时间才能得到计算 结果。比如在笔者的机器上,如果给定 N=100 000 000,则算出 f (N)大概需要 40 秒的时间,计算时间会随着 N 的增大而线性增 长。

方法二：

      假设 N=abcde,这里 a、b、c、d、e 分别是十进制数 N 的各 个数位上的数字。如果要计算百位上出现 1 的次数,它将会受到 三个因素的影响:百位上的数字,百位以下(低位)的数字,百 位(更高位)以上的数字。

       如果百位上的数字为 0,则可以知道,百位上可能出现 1 的次 数由更高位决定,比如 12 013,则可以知道百位出现 1 的情况可能 是 100~199,1 100~1 199,2 100~2 199,…,11 100~11 199, 一共有 1 200 个。也就是由更高位数字(12)决定,并且等于更高 位数字(12)×当前位数(100)。

       如果百位上的数字为 1,则可以知道,百位上可能出现 1 的次 数不仅受更高位影响,还受低位影响,也就是由更高位和低位共同 决定。例如对于 12 113,受更高位影响,百位出现 1 的情况是 100~ 199,1 100~1 199,2 100~2 199,…,11 100~11 199,一共 1 200 个,和上面第一种情况一样,等于更高位数字(12)×当前位数(100)。 但是它还受低位影响,百位出现 1 的情况是 12 100~12 113,一共 114 个,等于低位数字(123)+1。

       如果百位上数字大于 1(即为 2~9),则百位上可能出现 1 的次数也仅由更高位决定,比如 12 213,则百位出现 1 的可能性 为:100~199,1 100~1 199,2 100~2 199,…,11 100~11 199, 12 100~12 199,一共有 1 300 个,并且等于更高位数字+1(12+1) ×当前位数(100)。写成程序如下:

 public static int countOneByAlg(int num){

    int iCount =0,iFactor =1,iLowerNum =0,iCurrNum=0,iHigherNum=0;
    while(num/iFactor!=0){
        iLowerNum = num-(num/iFactor)*iFactor;
        iCurrNum = (num/iFactor)%10;
        iHigherNum = num/(iFactor*10);
        switch(iCurrNum){
            case 0: iCount+=iHigherNum*iFactor;
                break;
            case 1:
                iCount +=iHigherNum*iFactor+iLowerNum+1;
                break;
            default:
                iCount +=(iHigherNum+1)*iFactor;
                break;
        }
        iFactor*=10;

    }
    return iCount;
}

这个方法只要分析 N 就可以得到 f(N),避开了从 1 到 N 的 遍历,输入长度为 Len 的数字 N 的时间复杂度为 O(Len),即为 O(ln(n)/ln(10)+1)。在计算机上,计算 N=100 000 000相对于第一种方法的 40 秒时间,这种算法不到 1 毫秒就可以返回 结果,速度至少提高了 40 000 倍。

【完整的程序如下】：

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package countonejava;

/**
 *
 * @author MickeyChen
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static int countOneByAlg(int num){

    int iCount =0,iFactor =1,iLowerNum =0,iCurrNum=0,iHigherNum=0;
    while(num/iFactor!=0){
        iLowerNum = num-(num/iFactor)*iFactor;
        iCurrNum = (num/iFactor)%10;
        iHigherNum = num/(iFactor*10);
        switch(iCurrNum){
            case 0: iCount+=iHigherNum*iFactor;
                break;
            case 1:
                iCount +=iHigherNum*iFactor+iLowerNum+1;
                break;
            default:
                iCount +=(iHigherNum+1)*iFactor;
                break;
        }
        iFactor*=10;

    }
    return iCount;
}

public static int countOneByOne( int num){
    int count = 0;

    for(int i = 0;i <= num; i++){

        int tmp = i;
        while(tmp != 0){
            if(tmp % 10 == 1)
            count++;
        tmp/=10;

        }
    }
    return count;
}
    public static void main(String[] args) {
       int num = 60000;
       System.out.println("第一种算法"+countOneByOne(num));
       System.out.println("第二种算法"+countOneByAlg(num));
    }

}