Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example:
Input: n = 10 Output: 12 Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note:
1 is typically treated as an ugly number. n does not exceed 1690.
所有丑数的全集一定由2,3,5的倍数组成的集合以及1构成 由于要按顺序输出丑数，即丑数集合要具有单调性 枚举每个数字的倍数，显然一个数字的倍数集合单调递增 维护三个指针每次选最小的数加入丑数集即可 由于一个丑数可能同时存在于两个倍数集中，如6=2∗3=3∗2 6=23=326=2∗3=3∗2 所以每当找到一个当前最小的丑数，要让所以等于这个丑数的指针++ 复杂度O(n)
class Solution { public int nthUglyNumber(int n) { int[] results = new int[n]; results[0] = 1; int p2 = 0; int p3 = 0; int p5 = 0; for (int i = 1; i < n; i++) { int cur = Math.min(results[p2] * 2, Math.min(results[p3] * 3, results[p5] * 5)); results[i] = cur; if (cur == results[p2] * 2) { p2++; } if (cur == results[p3] * 3) { p3++; } if (cur == results[p5] * 5) { p5++; } } return results[n - 1]; } }