剑指offer----整数中1出现的个数

题目：求出1_{13的整数中1出现的次数,并算出100}1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。
方法1：分别计算然后加到一起O(nlgn) 不推荐

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int sum = 0;
        for(int i = 1; i <= n; i++){
            sum += helper(i);
        }
        return sum;
    }
    public int helper(int n){
        int sum = 0;
        while(n != 0){
            sum += (n % 10) == 1 ? 1 : 0;
            n /= 10;
        }
        return sum;
    }
}

下面这个算法可以做到O(n)
来源于寻找的一些规律
在1-n上所有的数字放在一起统计，
某个位上出现的的1的个数
分为三种情况（参数为n）

当n的该位数字为0时，该位上所有的1的总和仅仅与高位有关，等于（高位数字 x 当前位数）
当n的该位数字为1时，该位上所有的1的总和与高位数字和低位数字有关，等于（高位数字 x 当前位数） + 低位数字 + 1
当n的该位数字大于1上，该位上的所有的1的总和仅与高位有关，等于（高位数字加一 x 当前位数）

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int iCount = 0;
        int iFactor = 1;
        int iLowerNum = 0;
        int iCurrNum = 0;
        int iHigherNum = 0;
//12345 / 100 * 100 = 12300，      12345 - 12300 = 45 获取低位数
//12345 / 100 = 123，              123 % 10 = 3   获取高位数
//12345 / 1000 = 12
        while(n / iFactor != 0){
            iLowerNum = n - n / iFactor * iFactor;
            iCurrNum  = (n / iFactor) % 10;
            iHigherNum = n / (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;
    }
}