Ugly Number

    源码分析

    判断丑数时依次约掉质因数3，5，7，若处理完所有质因数3,5,7后不为1则不是丑数。自增 num 时应在判断是否为丑数之前。

    无法准确分析，但是估计在 O(n^3) 以上。

    我大概做了下尝试，首先根据丑数的定义可以写成 Uk = 3^{x_3} \cdot 5^{x_5} \cdot 7^{x_7}, 那么 U{k+1} 和 Uk 的不同则在于 x_3, x_5, x_7 的不同，递推关系为 U{k+1} = U_k \cdot \frac{3^{y_3} \cdot 5^{y_5} \cdot 7^{y_7}}{3^{z_3} \cdot 5^{z_5} \cdot 7^{z_7}},将这些分数按照从小到大的顺序排列可在 O(K) 的时间内解决，但是问题来了，得到这些具体的 y, z 就需要费不少时间，且人工操作极易漏解。:( 所以这种解法只具有数学意义，没有想到好的实现方法。

    除了这种找相邻递推关系的方法我们还可以尝试对前面的丑数依次乘3, 5, 7，直至找到比当前最大的丑数大的一个数，对乘积后的三种不同结果取最小值即可得下一个最大的丑数。这种方法需要保存之前的 N 个丑数，由于已按顺序排好，天然的二分法。

    C++

    Golang

    复杂度分析

    找下一个丑数 O(\log K), 循环 K 次，故总的时间复杂度近似 O(K \log K), 使用了数组保存丑数，空间复杂度 O(K).

    TBD