[LeetCode] 264. Ugly Number II 丑陋数 II

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

新题中没有提示，老版的有。

Hint:

1. The naive approach is to call isUgly for every number until you reach the n one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
2. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
3. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L, L, and L.
4. Assume you have U, the k ugly number. Then U must be Min(L * 2, L * 3, L * 5).

写一个程序找到第n个丑陋数，根据提示，丑陋数序列可以拆分为下面的子列表：

(1) 1x2,  2x2, 2x2, 3x2, 3x2, 4x2, 5x2...

(2) 1x3,  1x3, 2x3, 2x3, 2x3, 3x3, 3x3...

(3) 1x5,  1x5, 1x5, 1x5, 2x5, 2x5, 2x5...

每个子列表都是一个丑陋数分别乘以2,3,5，而要求的丑陋数就是从已经生成的序列中取出来的，每次都从三个列表中取出当前最小的那个加入序列。

Java:

public class Solution {

    public int nthUglyNumber(int n) {

        int[] ugly = new int[n];

        ugly[0] = 1;

        int index2 = 0, index3 = 0, index5 = 0;

        int factor2 = 2, factor3 = 3, factor5 = 5;

        for(int i=1;i<n;i++){

            int min = Math.min(Math.min(factor2,factor3),factor5);

            ugly[i] = min;

            if(factor2 == min)

                factor2 = 2*ugly[++index2];

            if(factor3 == min)

                factor3 = 3*ugly[++index3];

            if(factor5 == min)

                factor5 = 5*ugly[++index5];

        }

        return ugly[n-1];

    }

}

Python:

def nthUglyNumber(self, n):

    ugly = [1]

    i2, i3, i5 = 0, 0, 0

    while n > 1:

        u2, u3, u5 = 2 * ugly[i2], 3 * ugly[i3], 5 * ugly[i5]

        umin = min((u2, u3, u5))

        if umin == u2:

            i2 += 1

        if umin == u3:

            i3 += 1

        if umin == u5:

            i5 += 1

        ugly.append(umin)

        n -= 1

    return ugly[-1]　

C++:

class Solution {

public:

    int nthUglyNumber(int n) {

        if(n <= 0) return false; // get rid of corner cases

        if(n == 1) return true; // base case

        int t2 = 0, t3 = 0, t5 = 0; //pointers for 2, 3, 5

        vector<int> k(n);

        k[0] = 1;

        for(int i  = 1; i < n ; i ++)

        {

            k[i] = min(k[t2]*2,min(k[t3]*3,k[t5]*5));

            if(k[i] == k[t2]*2) t2++;

            if(k[i] == k[t3]*3) t3++;

            if(k[i] == k[t5]*5) t5++;

        }

        return k[n-1];

    }

};　　

C++:

class Solution {

public:

    int nthUglyNumber(int n) {

        vector<int> res(1, 1);

        int i2 = 0, i3 = 0, i5 = 0;

        while (res.size() < n) {

            int m2 = res[i2] * 2, m3 = res[i3] * 3, m5 = res[i5] * 5;

            int mn = min(m2, min(m3, m5));

            if (mn == m2) ++i2;

            if (mn == m3) ++i3;

            if (mn == m5) ++i5;

            res.push_back(mn);

        }

        return res.back();

    }

};

　　

类似题目：

[LeetCode] 263. Ugly Number 丑陋数

[LeetCode] 313. Super Ugly Number 超级丑陋数

All LeetCode Questions List 题目汇总