题目描述
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
解题思路
- 由于只含质因子2，3，5，那么可以知道，每一个丑数都是由这三个数互相做乘法而来的。
- 我们定义三个指针n2Index，n3Index，n5Index，每一次只需要比较n2Index * 2，n3Index * 3，n5Index * 5，拿到最小的那一个，更新为下一个丑数。将最小的那个指针下标 n*Index + 1。
class Solution {
public int nthUglyNumber(int n) {
int n2Index = 0;
int n3Index = 0;
int n5Index = 0;
final ArrayList<Integer> ugly = new ArrayList<>();
ugly.add(1);
for (int i = 1; i < n; i++) {
int n2 = ugly.get(n2Index) * 2;
int n3 = ugly.get(n3Index) * 3;
int n5 = ugly.get(n5Index) * 5;
int min = Math.min(Math.min(n2, n3), n5);
if (n2 == min) n2Index++;
if (n3 == min) n3Index++;
if (n5 == min) n5Index++;
ugly.add(min);
}
return ugly.get(n - 1);
}
}
