1~n 整數中 1 出現的次數

題目:

輸入一個整數 n, 求 1 ~ n 這 n 個整數的十進制表示中 1 出現的次數.

問題分析:

當 n 是最大的 k 位數時, 即 n=maxNumk

n=10k+1−1,sum(n)=k⋅10k−1

任何一位上的數字都可以是 0∼9 (位數不足的在前面補 0 , 如四位數的1表示為 0001 ), 可知, 0∼n 共有 k⋅10k 個 0∼9 之間的數字, 每個數字出現的次數必然相等, 是以有上式成立. 可以用以下方式表示, 令

h(k)=10⋅h(k−1),h(1)=1

則

h(k)=10k−1,k>0

故有

sum(maxNumk)=k⋅h(k),k≥1

為了讨論的友善, 将 n 記為 (nknk−1...n1), 其中 0≤ni≤9,nk≠0,i=k,k−1,...,1 . 對于任意的 ni 有如下公式:

sum(ni)=ni⋅(i−1)⋅h(i−1)+⎧⎩⎨⎪⎪⎪⎪⎪⎪0,nmodh(i)+1,h(i),ni=0ni=1ni>1

則可得

sum(n)=∑i=1ksum(ni)

案例:

n=10531

計算過程

個位數 1 : sum(11)=1∗(1−1)∗h(1−1)+nmodh(1)11=1+1=0+0+1=1 ;

十位數 3 : sum(32)=3∗(2−1)∗h(2−1)+h(2)32>1=3+10=13 ;

百位數 5 : sum(53)=5∗(3−1)∗h(3−1)+h(3)53>1=100+100=200 ;

千位數 0 : sum(04)=0∗(4−1)∗h(4−1)+004=0=0+0=0

萬位數 1 : sum(15)=1∗(5−1)∗h(5−1)+nmodh(5)15=1+1=4000+531+1=4532

則 sum(n) 如下:

sum(n)=∑i=15sum(ni)=1+13+200+0+4532=4746

根據上述思想及公式, C++代碼實作如下:

long NumberOf1(const int n)
{
    long sum = ;
    int m = n;

    for (int k = , hk = ; m > ; ++k)
    {
        int modK = m % ;
        sum = modK * k * (hk / );

        if (modK == )
            sum += n % hk + ;
        else if (modK > )
            sum += hk;

        m /= ;
        hk *= ;
    }

    return sum;
}
           

該算法的時間複雜度為 O(logN), 空間複雜度為 O(1).