只有素数因子为2,3或5的数字称为丑陋数字。
例：
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
1可以被认为是2 ^ 0。
我正在努力寻找第n个难看的数字。请注意，当n变大时，这些数字非常稀疏地分布。
我写了一个简单的程序来计算给定数字是否丑陋。对于n> 500 - 它变得超级慢。我尝试使用memoization - 观察：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;
}
我是第n个难看的数字。
即便这样也很慢。我想找到第1500个难看的数字。
一个简单的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)。
这是我的代码，想法是将数字除以2（直到它给出余数为0），然后是3和5。如果最后这个数字变为一个则是一个丑陋的数字。你可以数，甚至打印所有丑陋的数字，直到n。
def hamming(n: Int): Seq[BigInt] = {
@tailrec
def next(x: Int, factor: Int, xs: IndexedSeq[BigInt]): Int = {
val leq = factor * xs(x) <= xs.last
if (leq) next(x + 1, factor, xs)
else x
}
@tailrec
def loop(i: Int, j: Int, k: Int, xs: IndexedSeq[BigInt]): IndexedSeq[BigInt] = {
if (xs.size < n) {
val a = next(i, 2, xs)
val b = next(j, 3, xs)
val c = next(k, 5, xs)
val m = Seq(2 * xs(a), 3 * xs(b), 5 * xs(c)).min
val x = a + (if (2 * xs(a) == m) 1 else 0)
val y = b + (if (3 * xs(b) == m) 1 else 0)
val z = c + (if (5 * xs(c) == m) 1 else 0)
loop(x, y, z, xs :+ m)
} else xs
}
loop(0, 0, 0, IndexedSeq(BigInt(1)))
}
这个问题可以在O（1）中完成。
如果我们删除1并查看2到30之间的数字，我们会注意到有22个数字。
现在，对于上面22个数字中的任何数字x，在31到60之间将有一个数字x + 30也是丑陋的。因此，我们可以在31到60之间找到至少22个数字。现在对于31到60之间的每个丑陋数字，我们可以将其写为s + 30.因此s也将是丑陋的，因为s + 30可以被2,3整除因此，在31和60之间将恰好有22个数字。此后，对于每30个数字的块，可以重复该逻辑。
因此，前30个数字中将有23个数字，之后每30个数字将有22个数字。也就是说，前1到30 uglies将发生在1到30之间，45 uglies将发生在1到60之间，67 uglies将发生在1到30之间等。
现在，如果给我n，比如137，我可以看到137/22 = 6.22。答案将介于6 * 30和7 * 30之间或介于180和210之间。到180时，我将在180处获得6 * 22 + 1 = 133的丑陋数字。我将在210处获得第154个丑陋的数字。所以我在寻找区间[2,30]中的第4个丑陋的数字（因为137 = 133 + 4），这是5.第137个丑陋的数字则是180 + 5 = 185。
另一个例子：如果我想要第1500个丑陋的数字，我算上1500/22 = 68个块。因此，我将在30 * 68 = 2040时有22 * 68 + 1 = 1497个丑陋。[2,30]块中接下来的三个uglies是2,3和4.所以我们要求的丑陋是在2040 + 4 = 2044。
我可以简单地在[2,30]之间建立一个丑陋的数字列表，并通过在O（1）中进行查找来找到答案。
这是基于合并三个排序列表的想法的另一种O（n）方法（Python解决方案）。挑战在于以递增的顺序找到下一个丑陋的数字。例如，我们知道前七个丑陋的数字是http://www.geeksforgeeks.org/ugly-numbers/。丑陋的数字实际上来自以下三个列表：
所以第n个丑陋的数字是从上面三个列表中合并的列表的第n个数字：
1, 1*2, 1*3, 2*2, 1*5, 2*3 ...
#include <iostream>
#define MAX 1000
using namespace std;
// Find Minimum among three numbers
long int min(long int x, long int y, long int z) {
if(x<=y) {
if(x<=z) {
return x;
} else {
return z;
}
} else {
if(y<=z) {
return y;
} else {
return z;
}
}
}
// Actual Method that computes all Ugly Numbers till the required range
long int uglyNumber(int count) {
long int arr[MAX], val;
// index of last multiple of 2 --> i2
// index of last multiple of 3 --> i3
// index of last multiple of 5 --> i5
int i2, i3, i5, lastIndex;
arr[0] = 1;
i2 = i3 = i5 = 0;
lastIndex = 1;
while(lastIndex<=count-1) {
val = min(2*arr[i2], 3*arr[i3], 5*arr[i5]);
arr[lastIndex] = val;
lastIndex++;
if(val == 2*arr[i2]) {
i2++;
}
if(val == 3*arr[i3]) {
i3++;
}
if(val == 5*arr[i5]) {
i5++;
}
}
return arr[lastIndex-1];
}
// Starting point of program
int main() {
long int num;
int count;
cout<<"Which Ugly Number : ";
cin>>count;
num = uglyNumber(count);
cout<<endl<<num;
return 0;
}
int count = 0;
for (int i = 2; i <= n; i++) {
int temp = i;
while (temp % 2 == 0) temp=temp / 2;
while (temp % 3 == 0) temp=temp / 3;
while (temp % 5 == 0) temp=temp / 5;
if (temp == 1) {
cout << i << endl;
count++;
}
}
[1,2,3,4,5,6,8]def nthuglynumber(n):
p2, p3, p5 = 0,0,0
uglynumber = [1]
while len(uglynumber) < n:
ugly2, ugly3, ugly5 = uglynumber[p2]*2, uglynumber[p3]*3, uglynumber[p5]*5
next = min(ugly2, ugly3, ugly5)
if next == ugly2: p2 += 1 # multiply each number
if next == ugly3: p3 += 1 # only once by each
if next == ugly5: p5 += 1 # of the three factors
uglynumber += [next]
return uglynumber[-1]
ugly2, ugly3, ugly5 = uglynumber[p2]*2, uglynumber[p3]*3, uglynumber[p5]*5
next = min(ugly2, ugly3, ugly5)
注意：不使用if next == ugly2: p2+=1与if next == ugly3: p3+=1和if next == ugly5: p5+=1if中
elif我正在努力寻找第n个难看的数字。请注意，当n变大时，这些数字非常稀疏地分布。
我写了一个简单的程序来计算给定数字是否丑陋。
这看起来像是你试图解决的问题的错误方法 - 这是一个shlemiel算法。
您是否熟悉用于查找素数的Sieve of Eratosthenes算法？类似的东西（利用每个丑陋的数字是另一个丑陋数字的2,3或5倍的知识）可能更好地解决这个问题。
通过与Sieve的比较，我并不是说“保持一系列的bool并消除你上升的可能性”。我更多地指的是基于先前结果生成解决方案的一般方法。如果Sieve得到一个数字，然后从候选集中删除它的所有倍数，那么这个问题的一个好算法将从一个空集开始，然后将每个丑陋数字的正确倍数添加到那个。
我的回答是指Nikita Rybak给出的正确答案。因此，人们可以看到从第一种方法的想法转变为第二种方法的转变。
from collections import deque
def hamming():
h=1;next2,next3,next5=deque([]),deque([]),deque([])
while True:
yield h
next2.append(2*h)
next3.append(3*h)
next5.append(5*h)
h=min(next2[0],next3[0],next5[0])
if h == next2[0]: next2.popleft()
if h == next3[0]: next3.popleft()
if h == next5[0]: next5.popleft()
从Nikita Rybak的第一种方法改变的是，不是将下一个候选者添加到单个数据结构中，即树集，而是可以将它们中的每一个分别添加到3个FIFO列表中。这样，每个列表将一直保持排序，下一个最小候选者必须始终位于这些列表中的一个或多个列表的头部。
如果我们不再使用上面三个列表，我们将在Nikita Rybak的回答中得到第二个实现。这是通过仅在需要时评估那些候选者（包含在三个列表中）来完成的，因此不需要存储它们。
简单的说：
在第一种方法中，我们将每个新候选者放入单一数据结构中，这很糟糕，因为太多事情变得不明智。每次我们对结构进行查询时，这种糟糕的策略都不可避免地需要O（log（树大小））时间复杂度。但是，通过将它们放入单独的队列中，您将看到每个查询仅占用O（1），这就是整体性能降低到O（n）的原因！这是因为三个列表中的每一个都已经自行排序。
我相信你可以在亚线性时间内解决这个问题，可能是O（n ^ {2/3}）。
为了给你一个想法，如果你简化问题以允许只有2和3的因子，你可以通过搜索至少与2的最小幂来开始实现O（n ^ {1/2}）时间。第n个丑陋的数字，然后生成一个O（n ^ {1/2}）候选者列表。这段代码应该让你知道如何做到这一点。它依赖于这样的事实，即仅包含2和3的幂的第n个数具有素数因子分解，其指数之和为O（n ^ {1/2}）。
def foo(n):
p2 = 1 # current power of 2
p3 = 1 # current power of 3
e3 = 0 # exponent of current power of 3
t = 1 # number less than or equal to the current power of 2
while t < n:
p2 *= 2
if p3 * 3 < p2:
p3 *= 3
e3 += 1
t += 1 + e3
candidates = [p2]
c = p2
for i in range(e3):
c /= 2
c *= 3
if c > p2: c /= 2
candidates.append(c)
return sorted(candidates)[n - (t - len(candidates))]
同样的想法应该适用于三个允许的因素，但代码变得更加复杂。因子分解的幂的总和下降到O（n ^ {1/3}），但是你需要考虑更多的候选者，O（n ^ {2/3}）更精确。
基本上可以搜索On）：
考虑一下您保留丑陋数字的部分历史记录。现在，在每一步你必须找到下一步。它应该等于历史记录中的数字乘以2,3或5.选择最小的数字，将其添加到历史记录中，并从中删除一些数字，以便列表中的最小值乘以5将大于最大。
它会很快，因为搜索下一个数字很简单： min（最大* 2，最小* 5，中间* 3）， 它大于列表中的最大数字。如果它们很稀疏，列表将始终包含很少的数字，因此搜索必须乘以3的数字将很快。
这是ML中的正确解决方案。函数ugly（）将返回汉明数字的流（懒惰列表）。函数nth可以在此流上使用。
这使用Sieve方法，下一个元素仅在需要时计算。
datatype stream = Item of int * (unit->stream);
fun cons (x,xs) = Item(x, xs);
fun head (Item(i,xf)) = i;
fun tail (Item(i,xf)) = xf();
fun maps f xs = cons(f (head xs), fn()=> maps f (tail xs));
fun nth(s,1)=head(s)
| nth(s,n)=nth(tail(s),n-1);
fun merge(xs,ys)=if (head xs=head ys) then
cons(head xs,fn()=>merge(tail xs,tail ys))
else if (head xs<head ys) then
cons(head xs,fn()=>merge(tail xs,ys))
else
cons(head ys,fn()=>merge(xs,tail ys));
fun double n=n*2;
fun triple n=n*3;
fun ij()=
cons(1,fn()=>
merge(maps double (ij()),maps triple (ij())));
fun quint n=n*5;
fun ugly()=
cons(1,fn()=>
merge((tail (ij())),maps quint (ugly())));
这是CS工作的第一年:-)
为了找到O（n ^（2/3））中的第n个丑陋数字，jonderry的算法可以正常工作。请注意，涉及的数字很大，因此任何试图检查数字是否丑陋的算法都没有机会。
通过在O（n log n）时间和O（n）空间中使用优先级队列，可以轻松地按升序查找所有n个最小的丑陋数字：创建具有最小数字的数字优先级队列，最初仅包括编号1.然后重复n次：从优先级队列中删除最小的数字x。如果之前没有删除x，则x是下一个更大的丑陋数字，我们将2x，3x和5x添加到优先级队列。 （如果有人不知道术语优先级队列，那就像堆密码算法中的堆一样）。这是算法的开始：
1 -> 2 3 5
1 2 -> 3 4 5 6 10
1 2 3 -> 4 5 6 6 9 10 15
1 2 3 4 -> 5 6 6 8 9 10 12 15 20
1 2 3 4 5 -> 6 6 8 9 10 10 12 15 15 20 25
1 2 3 4 5 6 -> 6 8 9 10 10 12 12 15 15 18 20 25 30
1 2 3 4 5 6 -> 8 9 10 10 12 12 15 15 18 20 25 30
1 2 3 4 5 6 8 -> 9 10 10 12 12 15 15 16 18 20 24 25 30 40
执行时间证明：我们从队列中提取一个丑陋的数字n次。我们最初在队列中有一个元素，在提取一个丑陋的数字后，我们添加了三个元素，将数字增加2.因此，在找到丑陋的数字后，我们在队列中最多有2n + 1个元素。提取元素可以在对数时间内完成。我们提取的数字不仅仅是丑陋的数字，而且最多是丑陋的数字加上2n - 1个其他数字（那些在n-1步之后可能在筛子中的数字）。因此总时间小于3n项目删除，以对数时间= O（n log n），总空间最多为2n + 1个元素= O（n）。
这里有很多好的答案，但我很难理解这些，特别是这些答案中的任何一个，包括被接受的答案，都在Dijkstra's original paper中保留了公理2：
公理2.如果x在序列中，那么是2 * x，3 * x和5 * x。
在一些白板之后，很明显公理2在算法的每次迭代中都不是一个不变量，但实际上是算法本身的目标。在每次迭代中，我们尝试在公理2中恢复条件。如果last是结果序列S中的最后一个值，则公理2可以简单地重新描述为：
对于qazxsw poi中的一些qazxsw poi，qazxsw poi中的下一个值是
x，S和S的最小值，大于2x。我们称之为公理2'。
因此，如果我们能找到3x，我们可以在恒定时间内计算5x，last和x的最小值，并将其添加到2x。
但我们如何找到3x？一种方法是，我们不这样做;相反，每当我们向5x添加一个新元素S时，我们计算x，e和S，并将它们添加到最小优先级队列。由于此操作保证2e在3e中，因此简单地提取PQ的顶部元素满足公理2'。
这种方法有效，但问题是我们生成了一堆我们可能最终无法使用的数字。有关示例，请参阅5e答案;如果用户想要e（5）中的第5个元素，那个时刻的PQ持有S。我们可以不浪费这个空间吗？
事实证明，我们可以做得更好。我们只为每个倍数维护三个计数器，而不是存储所有这些数字，即this，S和6 6 8 9 10 10 12 15 15 20 25。这些是2i下一个号码的候选者。当我们选择其中一个时，我们只增加相应的计数器，而不是其他两个。通过这样做，我们不急切地产生所有的倍数，从而用第一种方法解决了空间问题。
让我们看看3j的干运行，即数字5k。我们从S开始，正如Dijkstra论文中的公理1所述。
n = 8注意9没有在迭代6增长，因为之前已经添加了最小候选1。为了避免必须记住所有先前元素的问题，我们修改算法以在相应的倍数等于最小候选者时递增所有计数器。这将我们带到以下Scala实现。
+---------+---+---+---+----+----+----+-------------------+
| # | i | j | k | 2i | 3j | 5k | S |
+---------+---+---+---+----+----+----+-------------------+
| initial | 1 | 1 | 1 | 2 | 3 | 5 | {1} |
+---------+---+---+---+----+----+----+-------------------+
| 1 | 1 | 1 | 1 | 2 | 3 | 5 | {1,2} |
+---------+---+---+---+----+----+----+-------------------+
| 2 | 2 | 1 | 1 | 4 | 3 | 5 | {1,2,3} |
+---------+---+---+---+----+----+----+-------------------+
| 3 | 2 | 2 | 1 | 4 | 6 | 5 | {1,2,3,4} |
+---------+---+---+---+----+----+----+-------------------+
| 4 | 3 | 2 | 1 | 6 | 6 | 5 | {1,2,3,4,5} |
+---------+---+---+---+----+----+----+-------------------+
| 5 | 3 | 2 | 2 | 6 | 6 | 10 | {1,2,3,4,5,6} |
+---------+---+---+---+----+----+----+-------------------+
| 6 | 4 | 2 | 2 | 8 | 6 | 10 | {1,2,3,4,5,6} |
+---------+---+---+---+----+----+----+-------------------+
| 7 | 4 | 3 | 2 | 8 | 9 | 10 | {1,2,3,4,5,6,8} |
+---------+---+---+---+----+----+----+-------------------+
| 8 | 5 | 3 | 2 | 10 | 9 | 10 | {1,2,3,4,5,6,8,9} |
+---------+---+---+---+----+----+----+-------------------+
我想我们可以使用动态编程（DP）并计算第n个丑陋数字。完整的解释可以在S找到
6我们可以看到它非常快，只需更改MAX的值来计算更高的Ugly数