1~n的连续整数有多少个1？

Posted on | | Visitors:

我自己在面试中遇到了这个题目，在面试过程中由于时间关系，自己当时只是描述了一下思路，后来我抽时间把这个思路实现了。这个过程我感觉比较有意思，所以决定分享一下。

开始旋转

暴力求解

这个就很简单了，循环对每个数的每一位上是否有1进行统计，下面是代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <sys/time.h>
#include <unistd.h>

int main(int argc, const char * argv[]) {
    while (scanf("%d",&n) != EOF) {
        long long ans = 0;
        struct timeval start, end;
        gettimeofday( &start, NULL );
        printf("start : %ld.%d\n", start.tv_sec, start.tv_usec);
        
        for (int i = 1; i <= n; i++) {
            int j = i;
            while (j) {
                if (j % 10 == 1) {
                    ans++;
                }
                j /= 10;
            }
        }
        
        printf("%lld\n",ans);
        gettimeofday( &end, NULL );
        printf("end   : %ld.%d\n", end.tv_sec, end.tv_usec);
    }
    return 0;
}

看看输出结果吧。

12345
start : 1516847188.935077
8121
end   : 1516847188.935670
12345678
start : 1516847301.275855
11824417
end   : 1516847302.203556

看到最后一个输出时间大概用了一秒钟，WTF！如果我们输入值是9位数，那就很酸爽了，反正我等了大半天没输出结果。

时间复杂度n(log10 n)

二分查找

当我们在把1~n的整数存起来的时候，其实就可以计算其中有多少个1了。不过这里还是可以看一下，从数据存储完成之后的计算需要多少时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <sys/time.h>
#include <unistd.h>

char c[10000000000];

void findone(int s, int e, long long *count) {
    if (s == e) {
        if (c[s] == 1) {
            (*count)++;
        }
    }
    else {
        int mid = (s + e) / 2;
        findone(s, mid, count);
        findone(mid+1, e, count);
    }
}

int main(int argc, const char * argv[]) {
    while (scanf("%d",&n) != EOF) {
        long long ans = 0;   
        int j = 0;
        for (int i = 1; i <= n; i++) {
            int temp = i;
            while (temp) {
                c[j] = temp % 10;
                j++;
                temp /= 10;
            }
        }
        
        struct timeval start, end;
        gettimeofday( &start, NULL );
        printf("start : %ld.%d\n", start.tv_sec, start.tv_usec);
        
        findone(0, j-1, &ans);
        printf("%lld\n",ans);
        
        gettimeofday( &end, NULL );
        printf("end   : %ld.%d\n", end.tv_sec, end.tv_usec);
    }
    return 0;
}

这个输出结果有点意外哦！

12345
start : 1516866437.180732
8121
end   : 1516866437.181642
12345678
start : 1516866444.616205
11824417
end   : 1516866445.753807

即使不算存储时间，还是很慢，而且跟预想中的时间复杂度有区别。理论上来说应该比暴力循环快的。

时间复杂度log2 N（N表示1~n的所有整数排列串长度）。

排列组合

由于1~n是连续的整数，也就是说这是一个有规律的排列，那么通过公式来计算肯定会比遍历查询快。

  • 假定输入数字长度为l，那么我们计算1个1、2个1…l个1的排列组合情况是不是就可以很高效地得出结果呢？

这里理想情况下每个位置的数是0~9的选择范围，所以在长度小于l的范围适用。

  • 那么l长度的排列又怎么处理呢？

设我们输入的数字为653453，在这中六位数的情况下，如果我们把最高位置为1，那么后面的五位数就可以当做一个五位数的全排列来计算，依次累加固定位为2、3、4、5的情况。最高位计算完之后在遍历次高位，再依次累加60、61、62、63、64的情况…以此类推，问题迎刃而解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <sys/time.h>
#include <unistd.h>

long long a[11][11];//表示当n<10^i有不同个数1的情况
int b[11];//表示按位存储当前n的值

//从p1中挑选p2个位置有多少种情况
int getCombinations(int p1, int p2) {
    int t = 1;
    for (int i = p1; i > p1-p2; i--) {
        t*=i;
    }
    int b = 1;
    for (int i = 1; i <= p2; i++) {
        b*=i;
    }
    return t/b;
}
//求p1的p2次幂
long long getPower(int p1, int p2) {
    long long ret = 1;
    while (p2) {
        if (p2 & 1) {
            ret *= p1;
        }
        p1 *= p1;
        p2 >>= 1;
    }
    return ret;
}

int main(int argc, const char * argv[]) {
    memset(a, 0, sizeof(a));
    int n;
    a[1][1] = 1;
    a[1][0] = 9;
    //i表示当前总共有几位数
    for (int i = 2; i <= 10; i++) {
        //使用j来表示当前有几位数是1
        int j = i;
        while (j>=0) {
            int k = i - j;
            a[i][j] = getPower(9, k) * getCombinations(i, j);
            j--;
        }
    }
    while (scanf("%d",&n) != EOF) {
        int tmp = n;
        int m = 1;
        /*
         这里我们分三步来计算1的个数。
         举个例子n=123
         1.计算0~99之间1的数量
         2.计算100~122之间1的数量
         3.计算123这个数包含1的数量
         */
        long long ans = 0;
        struct timeval start, end;
        gettimeofday( &start, NULL );
        printf("start : %ld.%d\n", start.tv_sec, start.tv_usec);
        //按位存储n的数值，并记录n包含多少个1
        while (tmp) {
            b[m] = tmp % 10;
            if (b[m] == 1) {
                ans++;
            }
            tmp /= 10;
            m++;
        }
        //利用我们我们预处理的组合来计算低于n一个数量级（10）的1的个数
        for (int j = 1; j < m-1; j++) {
            ans += a[m-2][j] * j;
        }
        //处理当前数量级的1的个数（不计算n本身）
        int num1 = 0;//记录高位1的个数
        for (int i = m-1; i > 0; i--) {
            if ((i==(m-1) && b[i] > 1) || (i<(m-1) && b[i] > 0)) {
                int j = b[i] - 1;
                while (i==m-1 ? j>0 : j>=0) {
                    if (j == 1 ) {
                        num1++;
                    }
                    if (i-1 > 0) {
                        for (int k = 0; k <= i-1; k++) {
                            ans += a[i-1][k] * (num1 + k);
                        }
                    }
                    else {
                        ans += num1;
                    }
                    if (j==1) {
                        num1--;
                    }
                    j--;
                }
            }
            if (b[i] == 1) {
                num1++;
            }
        }
        
        printf("%lld\n",ans);
        gettimeofday( &end, NULL );
        printf("end   : %ld.%d\n", end.tv_sec, end.tv_usec);
    }
    return 0;
}

晒出我们的输出时间。

12345
start : 1516867095.561999
8121
end   : 1516867095.562023
12345678
start : 1516867103.522433
11824417
end   : 1516867103.522456

哈哈，输出时间都在20微秒左右，应该算得上是一个比较好的方法吧。

时间复杂度(log10 n)3

提示：评论是disqus，需要使用请翻墙！