java算法----求从1到N中，某数出现的个数

这里提供一种基于数位分析的算法，可以求解从1到N中，某数k出现的个数。

具体步骤如下：

1. 将N拆分为高位和低位两部分，例如N=12345，高位为12，低位为345。

2. 对于k在高位和低位中的出现次数分别进行计算。

a. 高位中，k在最高位出现的次数为high=k>1?pow(10,len-1):(n%(int)pow(10,len-1)+1)，其中len为N的位数。

b. 低位中，k在每一位上出现的次数均为low=pow(10,i)，其中i为k所在的位数。

3. 最终结果为high*low，即为k在1到N中出现的总次数。

Java代码实现如下：

public static int countNumber(int n, int k) {
    int len = String.valueOf(n).length();
    int high, low, cur;
    int count = 0;
    for (int i = 1; i <= len; i++) {
        high = n / (int) Math.pow(10, len - i);
        cur = (n / (int) Math.pow(10, len - i - 1)) % 10;
        low = (int) Math.pow(10, len - i - 1);
        if (k == 0) {
            if (high > 1) {
                count += (high - 1) * low;
            }
            if (cur == k) {
                count += n % low + 1;
            }
        } else {
            if (high >= k) {
                count += high * low;
            }
            if (high == k && cur == 0) {
                count += n % low + 1;
            }
            if (high == k && cur != 0) {
                count += n % low + 1;
            }
            if (high < k) {
                count += (high + 1) * low;
            }
        }
    }
    return count;
}

这个算法的时间复杂度为O(logN)，空间复杂度为O(1)。