题解 | #丑数#

function GetUglyNumber_Solution(index) {
    if (index <= 6) {
        return index;
    }

    let ugly = [];
    ugly[0] = 1;
    let i2 = 0, i3 = 0, i5 = 0;//分别代表要乘上2 3 5的下标
    // 这个丑数数学形式是 2的x次方 * 3的y次方 * 5的z次方
    // 我们的函数做的事其实很简单，就是从xyz都等于0开始，依次试探性地增大xyz的值，每次取试探出来的最小的那个丑数。
    // 你完全就可以让xyz从0循环到30，排个序，这样就得到了30的立方个丑数。
    // 注意，这样生成的30的立方个丑数和用正常方法生成的30的立方个丑数是不一样的！！！
    // 因为有可能正常方法生成的丑数中，2的次方数已经比30还要大了，但是3和5的次方数更低，所以值比2，3，5各30次方要小！！！！
    // 所以这种暴力方法就没有一个不落地包含丑数数列中所有的值！
    // 我举这个例子只是说明一下我们要做的事：依次试探性地增大xyz的值，每次取试探出来的最小的那个丑数。
    // 顺便一提，xyz分别取30，19，13，用这种暴力且错误的方法能通过牛客的所有测试用例。。。。。

    // 你理解一下，这个i2 i3 i5它们增加的速度是没有ugly数组的长度增长快的。为什么？因为数组长度增长一，这三个中只有一个增长了一啊。
    // 另外两个是不动的。为什么要这样？你看for循环中的if判断部分，
    // 例如某一次循环中，i2++了，但i3，i5没有变，那么下次循环中我们判断的是ugly[i3] * 3这个值，ugly[i5] * 5这个值，以及第三个值
    // 但是第三个值ugly[i2] * 2中，由于i2++了，所以才导致了cur会取到不同的值。
    // 这里就是核心的地方，我们用i3，i5这两个变量间接地暂存了 上一次在三个丑数中选择最小丑数 的过程中，较大的那两个丑数，
    // 没错，上次的三个丑数分别是ugly[i2] * 2，ugly[i3] * 3，ugly[i5] * 5，
    // 但是这次循环中，三个丑数分别是ugly[i3] * 3，ugly[i5] * 5，和ugly[i2 + 1] * 2！
    // 也就是说，这次循环中在三个数中找最小丑数的过程，原来最小的那个已经添加过了，
    // 取而代之的是原来i2对应位置的下一个位置的丑数乘2的结果，这个数一定是变大了的
    // 如此一来，i3，i5对应的丑数在这次循环中才有机会成为最小从而被选中。如果上次选中的是i3或者i5是同理的。

    // 那可能会有问题，说会不会有两个丑数相等导致你这个选择过程选不出来导致bug呢？
    // 其实并不会。为什么？因为这是丑数的性质。2的x次方一定不等于3的y次方一定不等于5的z次方。不管你怎么取xyz。
    // 也就是说，不管你怎么试探xyz，没有两个丑数是相同的，丑数数列是一个递增的数列。

    for (let i = 1; i < index; i++) {
        let cur = Math.min(ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5);
        ugly[i] = cur;
        if (cur === ugly[i2] * 2) { // 假如说这次循环选择了ugly[i2] * 2，
            // 也就是说这次循环得到的新丑数是由ugly数组中i2位置对应的老丑数乘2得到的。
            // 换种理解方式，就像当于给i2对应位置的丑数x加一得到的新丑数比给i3位置的y加一和给i5位置的z加一得到的数都要小，所以选i2这个位置的。
            // 别搞混了，i2 i3 i5对应位置的丑数可不是一样的啊！每个位置对应一个不同丑数，每个丑数对应一套不同的xyz值！
            i2++; // 下次循环就要 用更大一点的那个丑数(继承它的xyz值) 乘2（x加一） 来与i3,i5各自对应的那个老丑数乘3、乘5比较。这样就有可能没它们小了对吧
        }
        if (cur === ugly[i3] * 3) {
            i3++;
        }
        if (cur === ugly[i5] * 5) {
            i5++;
        }
    }
    return ugly[index - 1];
}


module.exports = {
    GetUglyNumber_Solution: GetUglyNumber_Solution
};