第n个丑数

本文介绍了第n个丑数的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

号，其唯一的首要因素是2，3或5被称为难看号码。

Numbers whose only prime factors are 2, 3 or 5 are called ugly numbers.

例如：

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

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

1可以被认为是2 ^ 0

1 can be considered as 2^0.

我正在寻找第n个丑数。请注意，这些数字是非常稀疏分布为n变大。

I am working on finding nth ugly number. Note that these numbers are extremely sparsely distributed as n gets large.

我写了一个计算，如果给定的数字是丑，不是一个简单的程序。对于n> 500 - 它成为超慢。我试着用记忆化 - 观察：ugly_number * 2，ugly_number * 3，ugly_number * 5都是丑陋的。即使它是缓慢的。我试着用日志的一些性质 - 因为这将减少这个问题从乘法加法 - 但是，没有多少运气呢。想到跟大家分享这一点。任何有趣的想法？

I wrote a trivial program that computes if a given number is ugly or not. For n > 500 - it became super slow. I tried using memoization - observation: ugly_number * 2, ugly_number * 3, ugly_number * 5 are all ugly. Even with that it is slow. I tried using some properties of log - since that will reduce this problem from multiplication to addition - but, not much luck yet. Thought of sharing this with you all. Any interesting ideas?

使用类似的概念，以筛埃拉托色尼的（感谢匿名）

Using a concept similar to "Sieve of Eratosthenes" (thanks 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; }

我是第n个丑陋的数量。

i is the nth ugly number.

即使这是pretty的慢。我试图寻找第1500号难看。

Even this is pretty slow. I am trying to find 1500th ugly number.

推荐答案

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

A simple fast solution in Java. Uses approach described by Anon.. Here TreeSet is just a container capable of returning smallest element in it. (No duplicates stored.)

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个丑数为5120万，将它们存储在布尔[] 不是一个真正的选择。

Since 1000th ugly number is 51200000, storing them in bool[] isn't really an option.

修改 作为上下班（调试愚蠢休眠）消遣，这里是完全线性的解决方案。由于 marcog 的想法！

edit As a recreation from work (debugging stupid Hibernate), here's completely linear solution. Thanks to marcog for idea!

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 [1] ，我们可以使用 A [J] * 2 的一些 J＆LT;我。但是，我们还需要确保1） A [J] * 2 - ; A [1 - 1]。 2）Ĵ是最小的 然后， A [1] = MIN（A [J] * 2，[K] * 3，[T] * 5）。

The idea is that to calculate a[i], we can use a[j]*2 for some j < i. But we also need to make sure that 1) a[j]*2 > a[i - 1] and 2) j is smallest possible. Then, a[i] = min(a[j]*2, a[k]*3, a[t]*5).