题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。

例如 6、8 都是丑数，但 14 不是，因为它包含质因子 7。

求第 n 个丑数的值。

注意：习惯上我们把 1 当做第一个丑数。

样例

样例
输入：5

输出：5

(多路归并) $O(n)$

思路是有点类似与归并排序，两个有序数组，然后组成一个新的有序数组，建立两个指针，分别指向数组的开头，然后比较指针所对应的元素大小，取最小的元素，然后对应的指针前移动，这一题同样也是这样的，只是不同的是这是三个数组，属于多路归并，每个数组都是 丑数序列 * 2， *3， * 5，序列中的第一个元素是1.因此，每次我们只需要把指向i, j , k
指针对应元素的大小进行比较，取最小的，然后响应的跟最小值相等的指针进行前移，最后返回最后一个元素。

时间复杂度

参考文献

Java++ 代码

class Solution {
    public int getUglyNumber(int n) {
        int[] a = new int[n];
        int i= 0, j = 0, k = 0;
        a[0] = 1;
        for(int m = 1; m < n; m ++)
        {
            a[m] = Math.min(Math.min(2 * a[i], 3 * a[j]), 5 * a[k]);
            // System.out.println(a[m]);
            if(a[m] == 2 * a[i]) i ++;
            if(a[m] == 3 * a[j]) j ++;
            if(a[m] == 5 * a[k]) k ++;
        }
        return a[n - 1];
        }
}