一：解题思路
定义三个游标，p2,p3,p5,分别指向用来乘以2,3,5中的数组元素，然后取其最小值，加入到丑数数组中来。
Time:O(n),Space:O(n)
二：完整代码示例 (C++版和Java版)
C++:
class Solution { private: int min3(int a, int b, int c) { return min(min(a,b),c); } public: int nthUglyNumber(int n) { if (n <= 0) return -1; vector<int> uglyNum(n,0); int p2 = 0, p3 = 0, p5 = 0; uglyNum[0] = 1; for (int i = 1; i < n; i++) { int minValue = min3(2*uglyNum[p2],3*uglyNum[p3],5*uglyNum[p5]); uglyNum[i] = minValue; if (minValue == 2 * uglyNum[p2]) p2++; if (minValue == 3 * uglyNum[p3]) p3++; if (minValue == 5 * uglyNum[p5]) p5++; } return uglyNum[n-1]; } };
Java:
class Solution { private int min(int a,int b,int c) { return Math.min(Math.min(a,b),c); } public int nthUglyNumber(int n) { if(n<=0) return -1; int[] uglyNums=new int[n]; uglyNums[0]=1; int p2=0,p3=0,p5=0; for(int i=1;i<n;i++) { int minValue=min(2*uglyNums[p2],3*uglyNums[p3],5*uglyNums[p5]); uglyNums[i]=minValue; if(minValue==2*uglyNums[p2]) p2++; if(minValue==3*uglyNums[p3]) p3++; if(minValue==5*uglyNums[p5]) p5++; } return uglyNums[n-1]; } }
原文：https://www.cnblogs.com/repinkply/p/12700904.html