经典C面试题 -- 寻找丑数

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

分析：
按丑数定义，一个丑数只包含2、3、5这三个因数，因此，如果一个数是丑数，那么我们循环除以2、3、5直到最后肯定能够除尽。那么判断一个数是否是丑数就比较容易了（采用碾除法）：
static int isUglyNum(unsigned long long key)
{
     unsigned long long num = key;
     if (num == 0)
         return 0;

     while(num % 2 == 0)
         num /= 2;

     while(num % 3 == 0)
         num /= 3;

     while (num %5 == 0)
         num /= 5;

      return (num == 1);
}

在此基础上，按最通常的做法就是依次遍历正整数，验证每个数是否是丑数，然后统计验证成功的个数：

void printUglyNumbers(int cnt)
{
        unsigned long long key = 1;
        int cntSum = 0;

        while (cntSum <= cnt)
        {
                if (isUglyNum(key))
                {
                        cntSum++;
                        if (cntSum % 10 == 0)
                        {
                                printf("\t-->%d\n", cntSum);
                        }
                        printf("%lld ", key);
                }
                key++;
        }
}

上面实现把前@cnt个丑数打印出来。

分析到此，此题已经解了。so easy？ 如果有人和笔者一样编译运行过，那么会发现一个问题：打印前1500个会花分几秒钟的时间，打印前2000个会花费1分钟左右的时间，打印3000个笔者已经没有耐心等待它运行完毕......不错，上面的实现在@cnt较大时效率很低！

原因很简单：不难想象，丑数在数轴上是离散分布的，越是到大数部分，丑数分布越是分散。举个例子，假如A,B,C是数轴上三个相邻的丑数，那么由A,B,C的为基础的“发展出来”的新的丑数为【2A，2B,2C,3A,3B,3C,5A,5B,5C】，即使不考虑2C，3B，5A可能存在重复，就下界2A和上界5C所确定的域已经较之前A和C确定的域宽了很多（实际上是不平滑的指数级增长）。

重新考虑丑数的定义，可以推导出：一个丑数，必然是[2,3,5]这三个因子的其中一个，进过一步或多步因子[2,3,5]相乘得来的。比如10，就是因子2进过一步乘因子5得来的。我们把【2,3,5】作为基本集合，那么在此基础上经过一步因子乘操作可得集合（实际上【2,3,5】可以看做是【1】经过一次乘操作得来的，所以我们把【2,3,5】定为1阶集合，在此基础上做因子乘得2阶集合）：
2阶：【4,6,10,  6,9,15,  10,15,25】，排序出重复后为【4,6,9,10,15,25】
在2阶的基础上，进过一步因子相乘操作可得3阶集合：
3阶：【8,12,18,20,30,50,   12,18,27,30,45,75,   20,30,45,50,75,125】，排序、去重复后为【8,12,18,20,27,30,35,45,50,75,125】
......
k阶：是（k-1）阶集合中每个元素依次乘2,3,5后的集合经过排序去重，k阶元素都可以分解为（k+1）个因子相乘。

为了对比我们重列一下前几阶的丑数：
0阶：【1】
1阶：【2,3,5】
2阶：【4,6,9,10,15,25】
3阶：【8,12,18,20,27,30,35,45,50,75,125】

通过观察分析，可以发现以下几个特征：
1. 低阶和高阶之间不会有重复的元素（因为每一阶因子个数不一样）；
2. 低阶和高阶元素之间大小存在交叉，且交叉部分是高阶的较小的部分；
3. 每一阶集合域的下界是2^(k)，上界是5^(k)；
4. 如果，第i阶集合的上界小于第j阶集合的下界，那么第i阶集合与第j阶集合必然不会出现元素大小交叉。

回到我们题目，要求找出第N个丑数，假设我们已经依次求解k阶集合，且每一阶集合元素个数为len[k]，如果这k阶集合满足：
        （1）前i阶集合元素个数累加和大于等于N；
       （2）i阶集合的上界小于（k+1）阶集合的下界（即（k+1) 阶和i阶不存在交叉，那么在前k阶集合中，包含了由i阶集合上界所确定的范围【1，2，...，5^i】的所有丑数）
那么，我们将前k阶集合进行归并排列，SUM（len[0]....len[i]）长度的数组所包含的丑数一定是连续递增的，且个数大于等于N。于是我们从该数组中取出第N个即可。

根据分析，不难写出实现代码：
unsigned long long printUglyNumbersV2(int cnt)
{
    unsigned long long *pRcd;
    unsigned long long *pStep;
    unsigned long long *pAss;
    unsigned long long *pTemp;

    int idxr;
    int idxs;
    int step = 0;
    int stepi = 0;  // 记录第i阶时满足 SUM（len[i]) >= cnt
    int stepLen; 

    // 用于归并合并
    int idx2,idx3,idx5,index;
    unsigned long long key2, key3, key5, keys,keyr; 

    int i,j;

    int lenCnt = 0;
    unsigned long int memSizeByte = 0;

    pRcd = (unsigned long long*)calloc(cnt + 1, sizeof(unsigned long long));
    pStep = (unsigned long long*)calloc(cnt + 1, sizeof(unsigned long long));
    pAss = (unsigned long long*)calloc(cnt + 1, sizeof(unsigned long long));

    memSizeByte = sizeof(unsigned long long ) * (cnt + 1);

    pRcd[0] = 1;
    lenCnt = 1;

    pStep[0] = 1;
    stepLen = 1;

    while(lenCnt < cnt || (stepi != 0 && power(2, step) < power(5, stepi)))
    {
        // 遍历上一阶集合元素，归并排列下一阶集合
        idxs = 0;
        idx2 = idx3 = idx5 = 0;
        pStep[stepLen] = pStep[stepLen -1] * 30; // add a max determinant, as the end flag

        while( (idx2 < stepLen || idx3 < stepLen || idx5 < stepLen) && idxs < cnt)
        {
            key2 = pStep[idx2] * 2;
            key3 = pStep[idx3] * 3;
            key5 = pStep[idx5] * 5;

            if (key2 <= key3 && key2 <= key5)
            {
                pAss[idxs++] = key2;
                idx2++;

                if (key2 == key3)
                    idx3++;

                if (key2== key5)
                    idx5++;
            }
            if (key3 <= key5 && key3 < key2)
            {
                pAss[idxs++] = key3;
                idx3++;

                if (key3 == key5)
                    idx5++;
            }


            if (key5 < key2 && key5 < key3)
            {
                pAss[idxs++] = key5;
                idx5++;
            }
        }

        // 新一阶统计完毕，交换指针
        stepLen = idxs;
        pTemp = pAss;
        pAss = pStep;
        pStep = pTemp;
        bzero(pAss, memSizeByte);
        step++;

        // 合并新生成的一阶元素到记录中
        idxr = idxs = 0;
        index = 0;
        while( (idxr < lenCnt || idxs < stepLen) && index < cnt)
        {
            if (idxr == lenCnt)
            {
                while(idxs < stepLen)
                    pAss[index++] = pStep[idxs++];

                break;
            }
            if (idxs == stepLen)
            {
                while(idxr < lenCnt)
                    pAss[index++] = pRcd[idxr++];

                break;
            }

            if (pRcd[idxr] < pStep[idxs])
            {
                pAss[index++] = pRcd[idxr++];
            }
            else // 没有相等的
            {
                pAss[index++] = pStep[idxs++];
            }
        }

        // 新一阶集合合并完毕，交换指针
        lenCnt = index;
        if (lenCnt >= cnt)
        {
            if (!stepi)
            {
                stepi = step;
                printf("Mr.i : %d\n", stepi);
            }
        }

        pTemp = pAss;
        pAss = pRcd;
        pRcd = pTemp;

        bzero(pAss, memSizeByte);
    }

    //
    for(i = 0; i< cnt; i++)
    {
        if (i !=0 && i % 10 == 0)
            printf("\t--%d\n", i);

        printf("%lld ", pRcd[i]);
    }
    printf("\t--%d\n", i);

    keyr = pRcd[cnt-1];
    free(pRcd);
    free(pAss);
    free(pStep);
    return keyr;
}

经测试，打印前4000个丑数瞬间完成！