2018-01-18 计算第n个丑数

1. 题目:
   找出只含素因子2，3，5 的第 n 小的数。

//求最小数
int min(int a1, int a2, int a3) {
    printf("a1 = %d ,a2 = %d , a3 = %d\n", a1, a2, a3);
    return a1 < a2 ? ((a1 < a3) ? a1 : a3) : ((a2 < a3) ? a2 : a3);

}

int nthUglyNumber(int n) {
    if (n == 1) {
        return 1;
    }

    int *p = (int *) malloc(sizeof(int) * n);
    *p = 1;
    int *p2 = p;
    int *p3 = p;
    int *p5 = p;
    int count = 1;
    int result = 0;
    while (count < n ) {
        int val = min((*p2) * 2, (*p3) * 3, (*p5) * 5);
        printf("val -- %d\n", val);
        if (val == *p2 * 2) {
            p2++;
        }
        if (val == *p3 * 3) {
            p3++;
        }
        if (val == *p5 * 5) {
            p5++;
        }
        *(p + count) = val;
        count++;
    }
    result = *(p + n - 1);
    free(p);
    return result;
}

思路:
从最小的丑数算起,丑数是可以一直一直算出来的.
第一个丑数是1 ,下二个丑数是前面所有丑数 乘 2 或者 乘3 或者乘5 的最小值算出.
例:
第一个丑数是 1
下一个丑数 : 1 * 2 ,1 * 3, 1 * 5 中的最小数 ---> 1 * 2;
下一个丑数: 1 * 2 ,1 * 3 ,1 * 5 ,2 * 2,2 * 3,2 * 5 中最小的数 -->1 * 3;
下一个丑数: 1 * 2 , 1 * 3 ,1 * 5 ,2 * 2,2 * 3,2 * 5, 3 * 2,3 * 3,3 * 5中最小的数--->2 * 2

发现我们只要找出最小的一个.
其实第二次比较中,1 * 2 已经不用比较,因为现在的丑数已经是1 * 2 了,2 * 3,2 * 5 也不用比较,因为他们肯定比1 * 3,1 * 5 大 .
第三次比较,1 * 2,1 * 3 不用比较,因为现在的丑数已经是1 * 3 了,2 * 5, 3 * 2,3 * 3,3 * 5也不用比较,因为他们肯定比,1 * 5,2 * 2,2 * 3,2 * 5 大.

画图:
指针2 ,指针3 ,指针5 代表指向的值要乘以几

初始状态

初始状态,指针2 ,3 ,5 都指向1 .
比较 1 * 2,1 * 3,15 , 12 最小

第一次比较后
指针2 位置加一,并且设置新的丑数为2

下一次比较:
2 * 2 ,1 * 3 ,1 * 5 1 * 3最小,指针 3 的位置加1 ,并设置新的丑数为3

第二次比较后

直到最后求出第n个丑数.