描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。

数据范围：0≤n≤2000

要求：空间复杂度 O(n)， 时间复杂度 O(n)

示例

// 输入：
7
// 返回值：
8

解题思路

首先可以发现丑数存在的规律

• 前 20 个丑数：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36
• 丑数：u = 2^a 3^b 5^c

将所有丑数按顺序存入数组 data 中
第一个丑数为 1，则：data[0] = 1
下一个丑数是：data[0]*2 data[0]*3 data[0]*5 中的最小的一个，即 data[0]*2=2
所以，下一个丑数为：x=data[a] * 2    y=data[b] * 3    z=data[c] * 5 中最小的一个
因为 2 已经乘了一次，所以 a 从 0 变为 1（a++）

代码实现

/**
 * [JZ49-中等] 丑数
 *
 * @param index int整型
 * @return int整型
 */
func getUglyNumber(index int) int {
    if index <= 6 {
        return index
    }
 
    a, b, c := 0, 0, 0
 
    data := make([]int, index)
    data[0] = 1
     
    for i := 1; i < index; i++ {
        min := data[a] * 2
        if t := data[b] * 3; t < min {
            min = t
        }
        if t := data[c] * 5; t < min {
            min = t
        }
        data[i] = min
        if min == data[a] * 2 {
            a++
        }
        if min == data[b] * 3 {
            b++
        }
        if min == data[c] * 5 {
            c++
        }
    }
    return data[index-1]
}