LintCode-4.丑数 II

丑数 II

设计一个算法，找出只含素因子2，3，5 的第 n 大的数。

符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

注意事项

我们可以认为1也是一个丑数

样例

如果n = 9，返回 10

挑战

要求时间复杂度为O(nlogn)或者O(n)

标签

LintCode 版权所有优先队列

code

class Solution {

public:

    /*

     * @param n an integer

     * @return the nth prime number as description.

     */

    int nthUglyNumber(int n) {

        // write your code here

        if(n <= 0)

            return 0;

        int *pivUglyNum = new int[n];

        int *piMul2=pivUglyNum, *piMul3=pivUglyNum, *piMul5=pivUglyNum;

        int nextNumIndex = 1;

        pivUglyNum[0] = 1;

        while(nextNumIndex < n) {

            int min = minIn3Num(*piMul2 * 2, *piMul3 * 3, *piMul5 * 5);

            pivUglyNum[nextNumIndex] = min;

            while(*piMul2 * 2 <= pivUglyNum[nextNumIndex])

                piMul2++;

            while(*piMul3 * 3 <= pivUglyNum[nextNumIndex])

                piMul3++;

            while(*piMul5 * 5 <= pivUglyNum[nextNumIndex])

                piMul5++;

            nextNumIndex++;

        }

        int uglyNum = pivUglyNum[nextNumIndex-1];

        delete[] pivUglyNum;

        return uglyNum;

    }

    int minIn3Num(int num1, int num2, int num3) {

        int min = (num1 < num2) ? num1 : num2;

        min = (min < num3) ? min : num3;

        return min;

    }

};

巴特西

LintCode-4.丑数 II

丑数 II

注意事项

样例

挑战

标签

code

最新文章

热门文章