第n个丑数

一尘不染

第n个丑数

algorithm

仅素数为2、3或5的数字称为丑数。

例：

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

1可以视为2 ^ 0。

我正在寻找第n个丑数。请注意，这些数字随着n变大而极为稀疏。

我写了一个琐碎的程序，计算给定数字是否丑陋。对于n > 500-它变得超级慢。我试着用记忆化-观察：ugly_number * 2，ugly_number * 3，ugly_number * 5都是丑陋的。即使这样它也很慢。我尝试使用log的某些属性-
因为这样可以减少从乘法到加法的问题-但还算运气。想与大家分享。有什么有趣的想法吗？

使用类似于 Eratosthenes筛网 的概念（感谢Anon）

    for (int i(2), uglyCount(0); ; i++) {
        if (i % 2 == 0)
            continue;
        if (i % 3 == 0)
            continue;
        if (i % 5 == 0)
            continue;
        uglyCount++;
        if (uglyCount == n - 1)
            break;
    }

i 是第n个丑数。

即使这很慢。我试图找到第1500个丑陋的数字。

阅读 222

2020-07-28

共1个答案

一尘不染

一个简单的Java快速解决方案。使用 Anon 描述的方法。。
这TreeSet只是一个能够返回其中最小元素的容器。（没有重复存储。）

    int n = 20;
    SortedSet<Long> next = new TreeSet<Long>();
    next.add((long) 1);

    long cur = 0;
    for (int i = 0; i < n; ++i) {
        cur = next.first();
        System.out.println("number " + (i + 1) + ":   " + cur);

        next.add(cur * 2);
        next.add(cur * 3);
        next.add(cur * 5);
        next.remove(cur);
    }

由于第1000个丑陋的数字是51200000，因此将它们存储在其中bool[]并不是真正的选择。

编辑
作为工作休闲（调试愚蠢的Hibernate），这是完全线性的解决方案。感谢 marcog 的想法！

    int n = 1000;

    int last2 = 0;
    int last3 = 0;
    int last5 = 0;

    long[] result = new long[n];
    result[0] = 1;
    for (int i = 1; i < n; ++i) {
        long prev = result[i - 1];

        while (result[last2] * 2 <= prev) {
            ++last2;
        }
        while (result[last3] * 3 <= prev) {
            ++last3;
        }
        while (result[last5] * 5 <= prev) {
            ++last5;
        }

        long candidate1 = result[last2] * 2;
        long candidate2 = result[last3] * 3;
        long candidate3 = result[last5] * 5;

        result[i] = Math.min(candidate1, Math.min(candidate2, candidate3));
    }

    System.out.println(result[n - 1]);

这个想法是为了计算a[i]，我们可以用a[j]*2一些j < i。但是我们还需要确保1）a[j]*2 > a[i - 1]和2）j最小。
然后，a[i] = min(a[j]*2, a[k]*3, a[t]*5)。

2020-07-28