本文共 1709 字，大约阅读时间需要 5 分钟。

题目描述如下：

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

开始想到之后的ugly number肯定是用已经求得的数乘以2、3、5得出，之后用三个循环分别求出每组的最小值；这样能AC，但是算法不够优化，时间复杂度是n的平方；

以下是代码：

public class Solution {

    public int nthUglyNumber(int n) { long[] dp = new long[n + 1]; if(n == 1) return 1; dp[1] = 1; for(int i = 2; i <=n ; i++){ long minFrom2 = minOfList(dp, 2, dp[i - 1]); long minFrom3 = minOfList(dp, 3, dp[i - 1]); long minFrom5 = minOfList(dp, 5, dp[i - 1]); dp[i] = Math.min(minFrom2, Math.min(minFrom3, minFrom5)); } return (int)dp[n]; } public long minOfList(long[] array, int factor, long minBound){ int len = array.length; long min = Long.MAX_VALUE; for(int i = 1; i < len && array[i] != 0; i++){ long temp = factor * array[i]; if(temp < min && temp > minBound) min = temp; }//end for i return min; } }

之后在网上找别人的代码，发现每次求每组数据的最小值的时候其实是不需要遍历的，因为dp数组里本来就是已经排好序的，所以按index往上使用就可以；这样时间复杂度是n；以下是代码：

public class Solution {

    public int nthUglyNumber(int n) { long[] dp = new long[n + 1]; if (n == 1) return 1; dp[1] = 1; long factor2 = 2, factor3 = 3, factor5 = 5; int index2 = 1, index3 = 1, index5 = 1; for (int i = 2; i <= n; i++) { long minNum = min(factor2, factor3, factor5); dp[i] = minNum; if(factor2 == minNum) factor2 = 2 * dp[++index2]; if(factor3 == minNum) factor3 = 3 * dp[++index3]; if(factor5 == minNum) factor5 = 5 * dp[++index5]; } return (int) dp[n]; } public long min(long factor2, long factor3, long factor5){ long temp =  (factor2 > factor3 ? factor3 : factor2); return temp > factor5 ? factor5 :  temp; } }

转载地址：http://gobvb.baihongyu.com/