大神求助，算法问题

Question

找出1到某个数的含有1这个数的个数，例如18，含有1的就是  1，11,12,13,14,15,16,17,18

Answer 1

不要效率的话，有个O(n^2)的算法。要效率，需要数论，有O(1)的算法。

Answer 2

class Main {
public static void main(String[] args) {
show(18);
} private static void show(int n) {
String tmp = "";
for (int i = 1; i <= n; i++) {
// int 转 string
tmp = String.valueOf(i);
// 打印包含1的整数
if (tmp.contains("1")) {
System.out.print(i + ", ");
}
}
}
}

Answer 3

你有两点错误,（1）直接遍历肯定不是o(n)tmp.contains("1")源码你看过吗,这个方法肯定不是o(1)的复杂度。所以n*!1 不是 o(n)这个你应该能看懂。(2)o(1)可能。
很多看似o(1)不可能，实际上数论就可以o(1)解决。退一步说，如果我能打一个足够大的表。我也能o(1)。别误导人。

Answer 4

contains()
最终最终依靠的是这个函数    static int indexOf(char[] source, int sourceOffset, int sourceCount,
                       char[] target, int targetOffset, int targetCount,
                       int fromIndex) {
if (fromIndex >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
}
     if (fromIndex < 0) {
         fromIndex = 0;
     }
if (targetCount == 0) {
    return fromIndex;
}        char first  = target[targetOffset];
        int max = sourceOffset + (sourceCount - targetCount);        for (int i = sourceOffset + fromIndex; i <= max; i++) {
            /* Look for first character. */
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                int j = i + 1;
                int end = j + targetCount - 1;
                for (int k = targetOffset + 1; j < end && source[j] ==
                         target[k]; j++, k++);                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }
        return -1;
    }
这个函数复杂度肯定不是o(1)你给的那个方法不是o(n)

Answer 5

大哥，那你最起码不能说。因为你掉个破函数复杂度就讲到o(n)了吧。这个问题遍历一打眼复杂度就是o(n^2)n个数，每个数看n位。要抬杠的话，我就没办法了。