leetcode筆記：Ugly Number II

leetcode筆記：Ugly Number II

一. 題目描述

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：
從1開始的丑數為：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … 該題的大意是，輸入一個正整數n，返回第n個丑數，這要求比起Ugly Number一題是復雜了些。

事實上，在觀察這些丑數組合時，無非是分成如下三種組合（其中，第一個乘數為上一次計算得出的丑數，第一個丑數為1，第二個乘數為2、3、5中的一個數）：

(以2為乘數)1×2, 2×2, 3×2, 4×2, 5×2, 6×2, 8×2, …
(以3為乘數)1×3, 2×3, 3×3, 4×3, 5×3, 6×3, 8×3, …
(以5為乘數)1×5, 2×5, 3×5, 4×5, 5×5, 6×5, 8×5, …

於是，開辟一個存放n個丑數的數組，在每次迭代時，從三種乘法組合中選取積最小的丑數並放入數組。最後數組的最後一個元素即是所求的丑數。

三. 示例代碼

class Solution
{
public:
    int nthUglyNumber(int n) {
        int* uglyNum = new int[n]; // 用於存放前n個丑數
        uglyNum[0] = 1;

        int factor2 = 2, factor3 = 3, factor5 = 5;
        int index2, index3, index5;
        index2 = index3 = index5 = 0;

        for(int i = 1; i < n; ++i)
        {
            // 取三組中的最小
            int minNum = min(factor2, factor3, factor5);
            uglyNum[i] = minNum;

            // 分三組計算
            if(factor2 == minNum)
                 factor2 = 2 * uglyNum[++index2];
            if(factor3 == minNum)
                 factor3 = 3 * uglyNum[++index3];
            if(factor5 == minNum)
                 factor5 = 5 * uglyNum[++index5];
        }
        int temp = uglyNum[n-1];
        delete [] uglyNum;
        return temp;
    }

private:
    // 求三個數的最小值
    int min(int a, int b, int c) {
        int minNum = a > b ? b : a;
        return minNum > c ? c : minNum;
    }
};