题目描述

我们把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如 6、8都是丑数，但 14不是，因为它包含质因子7。求第n个丑数的值。

样例

int getUglyNumber(int n) {
    if (n <= 0) {
        return 0;
    }
    // 用于存储丑数序列
    int *uglyNumbers = (int *)malloc(n * sizeof(int));
    if (uglyNumbers == NULL) {
        return -1;
    }
    // 第一个丑数为1
    uglyNumbers[0] = 1;
    // 三个指针，分别用于记录乘以2、3、5的情况
    int p2 = 0, p3 = 0, p5 = 0;
    for (int i = 1; i < n; ++i) {
        // 计算下一个可能的丑数，分别是当前丑数乘以2、3、5得到的
        int nextUgly2 = uglyNumbers[p2] * 2;
        int nextUgly3 = uglyNumbers[p3] * 3;
        int nextUgly5 = uglyNumbers[p5] * 5;
        // 取三者中的最小值作为下一个丑数
        uglyNumbers[i] = (nextUgly2 < nextUgly3)? ((nextUgly2 < nextUgly5)? nextUgly2 : nextUgly5) : ((nextUgly3 < nextUgly5)? nextUgly3 : nextUgly5);
        // 根据选择的最小值，相应地移动指针
        if (uglyNumbers[i] == nextUgly2) {
            p2++;
        }
        if (uglyNumbers[i] == nextUgly3) {
            p3++;
        }
        if (uglyNumbers[i] == nextUgly5) {
            p5++;
        }
    }
    int result = uglyNumbers[n - 1];
    free(uglyNumbers);
    return result;
}