剑指Offer——丑数

By AverageJoeWang
 标签:

丑数

  • 题目描述
    把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

  • 解题思路

动态规划,对于第i个数,它一定是之前已存在数的2倍,3倍或5倍

  • 代码实现
public class Solution {
    public int GetUglyNumber_Solution(int index) {
         if (index <= 0)
            return 0;
        int buf[] = new int[index];
        buf[0] = 1;
        int s1 = 0;
        int s2 = 0;
        int s3 = 0;
        for (int i = 1; i < index; ++i) {
            buf[i] = Math.min(buf[s1] * 2, Math.min(buf[s2] * 3, buf[s3] * 5));
            if (buf[i] == buf[s1] * 2) s1++;
            if (buf[i] == buf[s2] * 3) s2++;
            if (buf[i] == buf[s3] * 5) s3++;
        }
        return buf[index - 1];
    }
}