丑数

题目描述

设计一个算法,找出只含素因子235 的第 n 小的数。

符合条件的数如:1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

我们可以认为1也是一个丑数。

要求时间复杂度为O(nlogn)或者O(n)

问题分析

因子只含2,3,5,那么必然是1乘以2,3,5得出的数再不断地乘以2,3,5。但是这样得出的数是无序的,并且存在重复值的。那么这道题的难度就在于怎么取到第n小的数。

我们将获得的丑数放在一个ArrayList中,借用三个指针,p2,p3,p5,分别指向list的元素位置。每次都取2*list.get(p2),3*list.get(p3),5*list.get(p5)中最小的放进list,最小的那个的元素指针向后移动一个位置,比如2*list.get(p2),则p2+1。如此循环,直到将第n个数放入为止。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int nthUglyNumber(int n) {
List<Integer> uglyNumbers = new ArrayList<>(n);
uglyNumbers.add(1);

int p2 = 0;
int p3 = 0;
int p5 = 0;

for (int i = 1; i < n; i++) {
Integer lastNumber = uglyNumbers.get(i - 1);

while (uglyNumbers.get(p2) * 2 <= lastNumber) {
p2++;
}

while (uglyNumbers.get(p3) * 3 <= lastNumber) {
p3++;
}

while (uglyNumbers.get(p5) * 5 <= lastNumber) {
p5++;
}

uglyNumbers.add(Math.min(Math.min(uglyNumbers.get(p2) * 2, uglyNumbers.get(p3) * 3), uglyNumbers.get(p5) * 5));
}

return uglyNumbers.get(n - 1);
}
-------------本文结束感谢您的阅读-------------

本文标题:丑数

文章作者:huihui

发布时间:2018年11月08日 - 00:11

最后更新:2019年02月14日 - 19:02

原始链接:http://101.200.47.120:8011/2018/11/08/丑数/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。