2020-06-02 归并 264. Ugly Number I

https://leetcode.com/problems/ugly-number-ii
参考：https://www.cnblogs.com/grandyang/p/4743837.html

My answer / NAC

/**
 * @param {number} n
 * @return {number}
 */
var nthUglyNumber = function(n) {
    if(n==1) return 1;
    var merged=[], dp1 = [], dp2 = [], dp3 = [];
    dp1[0] = 2;
    dp2[0] = 3;
    dp3[0] = 5;
    for(let i=1; i<=1960; i++){
        dp1[i*3-2]=dp1[i-1]*2;
        dp1[i*3-1]=dp1[i-1]*3;
        dp1[i*3]=dp1[i-1]*5;
        
        dp2[i*3-2]=dp2[i-1]*2;
        dp2[i*3-1]=dp2[i-1]*3;
        dp2[i*3]=dp2[i-1]*5;
        
        dp3[i*3-2]=dp3[i-1]*2;
        dp3[i*3-1]=dp3[i-1]*3;
        dp3[i*3]=dp3[i-1]*5;
        
        merged = merge(dp1, dp2, dp3);
        
    }

    return merged[n-1];
};

var merge = function(a1, a2, a3) {
    return Array.from(new Set(a1.concat(a2, a3, [1]))).sort((a,b)=>a-b);
}

想出来了办法但是总是超时，卡在栈的优化处理上了。

Best answer

/**
 * @param {number} n
 * @return {number}
 */
var nthUglyNumber = function(n) {
    if(n==1) return 1;
    var merged=[1], i2=0, i3=0, i5=0;
    while(merged.length<n){
        var m2 = merged[i2]*2, m3 = merged[i3]*3, m5 = merged[i5]*5;
        var mn = Math.min(m2, Math.min(m3, m5));
        if(mn===m2) ++i2;
        if(mn===m3) ++i3;
        if(mn===m5) ++i5;
        merged.push(mn);

    }
    return merged.pop();
};

好在哪？

• 方法就是用如下3个子列表，3个变量存储答案数组merged的3个暂时的位置，代表乘数为2、3、5当前的被乘数的位置（因为丑陋数必须是由丑陋数乘2/3/5产生）。只有当前算出来的数是最小的才自增1并加进去答案的数组里，否则保持不变。m2 = merged[i2] * 2 意思是当前属于乘数为2的丑陋数为m2（下表的第一列，随后是乘数为3、5的丑陋数）。

(1) 1x2, 2x2, 2x2, 3x2, 3x2, 4x2, 5x2...
(2) 1x3, 1x3, 2x3, 2x3, 2x3, 3x3, 3x3...
(3) 1x5, 1x5, 1x5, 1x5, 2x5, 2x5, 2x5...

• 每次只有你是最小的（加粗的）你才会自增，否则保持当前被乘数位置。

Recap

了解到了一种船新的思路，被乘数位置表示的是当前所能取的最大值了（要等别的两个被乘数位置都超过我了，我才有机会再往上走，这样就不会漏掉丑陋数），利用三个变量来各自表示当前所到达的被乘数位置。