K路归并

算法思路图

如图所示：我们需要保存归并后的结果，使用数组f,k取2，3，5,表示有3条路，每条路的取值是f[f2]2,f[f3]4和f[f5]*5，其中f2,f3,f5分别表示的是当前这条路到达的索引位置。

class Solution {
    public int getUglyNumber(int n) {
        int f2 = 0, f3 = 0, f5 = 0;
        int[] f = new int[n];
        f[0] = 1;
        int i = 1;
        while(i < n){
            f[i] = Math.min(f[f2]*2,Math.min(f[f3]*3,f[f5]*5));
            // 为什么每个都需要进行if判断呢，因为可能出现重复数字，例如上图中的10就出现了两次
            if(f[i]%2 == 0) f2++;
            if(f[i]%3 == 0) f3++;
            if(f[i]%5 == 0) f5++;
            i++;
        }
        return f[n-1];
    }
}