首页 > 代码库 > 25.在从1到n的正数中1出现的次数

25.在从1到n的正数中1出现的次数

2024-07-05 08:17:21   223人阅读

http://zhedahht.blog.163.com/blog/static/25411174200732494452636/

http://www.cnblogs.com/GoAhead/archive/2012/05/28/2521415.html

http://blog.csdn.net/sjf0115/article/details/8600599

题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。

例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。

分析：这是一道广为流传的google面试题。

普通n*lg(n)的解法。

/////////////////////////////////////////////////////////////////////////////
// Find the number of 1 in an integer with radix 10
// Input: n - an integer
// Output: the number of 1 in n with radix
/////////////////////////////////////////////////////////////////////////////
int NumberOf1(unsigned int n)
{
    int number = 0;
    while(n)
    {
        if(n % 10 == 1)
            number ++;

        n = n / 10;
    }

    return number;
}

/////////////////////////////////////////////////////////////////////////////
// Find the number of 1 in the integers between 1 and n
// Input: n - an integer
// Output: the number of 1 in the integers between 1 and n
/////////////////////////////////////////////////////////////////////////////
int NumberOf1BeforeBetween1AndN_Solution1(unsigned int n)
{// T(n) = n*lg(n)
    int number = 0;

    // Find the number of 1 in each integer between 1 and n
    for(unsigned int i = 1; i <= n; ++ i)
        number += NumberOf1(i);

    return number;
}

更加巧妙的lg(n)的解法。

简单的方法就是按照给位进行分析:

在个位出现1的个数=n/10+(个位=0,0；个位>1,1;个位=1，低0位+1)；

十位位出现1的个数=n/100*10+(十位=0,0；十位>1,10；十位=1，低一位+1)；

百位出现1的个数=n/1000*100+(百位=0,0；百位>1,100;百位=1，低两位+1)；

等等

算法的复杂度仅仅和位数有关。

 

设第i位出现1的个数为s(i),N为输入整数n的位数。则总和sum= s(1)+…s(i)+…s(N)即为所求。

设bi为整数n的第i位数字，第i位之后的剩余数字为ri;

s(i) = A + B

A = n/10i*10i-1

bi=( n/10i-1)%10

ri= n/10i-1

b(i)==0 ,则B=0

b(i)==1 ,则B=ri+1

b(i)>1 ,则B=10i-1

int PowerBase10(unsigned int n)
{// 10^n
    int result = 1;
    for(unsigned int i = 0; i < n; ++ i)
        result *= 10;

    return result;
}

int b10(unsigned int n)
{
    return PowerBase10(n);
}

int NumberBitCount(unsigned int n)
{
    int N = 0;
    while(n)
    {
        n = n/10;
        N++;
    }
    return N;
}

int NumberOf1BeforeBetween1AndN_Solution2(unsigned int n)
{// T(n) = o(N) = o(lgn)
    int N = NumberBitCount(n);
    int si,sum=0;
    int A,B,bi,ri;
    for (int i=1;i<=N;i++)
    {
        A = n/b10(i)*b10(i-1);
        bi = n/b10(i-1)%10;
        ri = n%b10(i-1);
        if (bi==0)
        {
            B = 0;
        }
        else if (bi==1)
        {
            B = ri+1;
        }
        else if (bi>1)
        {
            B = b10(i-1);
        }
        si = A+B;
        sum +=si;
    }

    return sum;
}


联系
我们