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

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. 

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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. 1 is typically treated as an ugly number.
  2. n does not exceed 1690. 

题目大意：

寻找第n个丑数，n不超过1690。

解法：

将找到的丑数记录在一个数组中，返回第n个丑数，后面的丑数一定是前面的丑数生成的，一定是前面某个丑数×2、前面某个丑数×3、前面某个丑数×5这三个数中的一个最小值，使用index2，index3，index5的需要×2，×3，×5下标的数字，将生成的丑数继续加到数组中。

java:

class Solution {
    public int nthUglyNumber(int n) {
        int index2=0,index3=0,index5=0;
        int[] res=new int[n];
        res[0]=1;
        for (int i=1;i<n;i++){
            res[i]=Math.min(res[index2]*2,Math.min(res[index3]*3,res[index5]*5));
            if (res[i]==res[index2]*2) index2++;
            if (res[i]==res[index3]*3) index3++;
            if (res[i]==res[index5]*5) index5++;
        }

        return res[n-1];
    }
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄