[Leetcode] 264. Ugly Number II

这题的最优解其实有点类似于merge sorted lists。虽然看起来完全不是一道题，但思路上是有承继的。

首先，整个ugly numbers的列表，肯定是由2，3，5的乘积组成的（1除外），不可能有别的数字。

假设我们先列10个base case

1，2，3，4，5，6，8，9，10，12
然后作如下处理

1, 1 * 2，2 * 2，3 * 2，4 * 2，5 * 2，6 * 2，8 * 2，9 * 2，10 * 2，12 * 2 ...  (arr2)
1, 1 * 3，2 * 3，3 * 3，4 * 3，5 * 3，6 * 3，8 * 3，9 * 3，10 * 3，12 * 3 ...  (arr3)
1, 1 * 5，2 * 5，3 * 5，4 * 5，5 * 5，6 * 5，8 * 5，9 * 5，10 * 5，12 * 5 ... (arr5)

我们得到了三个数组。分别是结果数组乘以2，乘以3，和乘以5的结果。
再然后，我们可以发现，其实整个ugly number的数组，就是这样三个数组的lists merge sort...

假设我们三个数组里面先都只有1。结果数组里有1。然后数组往外扩展，变成了

1 ,2
1 ,3
1 ,5

在这3个数组的新数字里，2最小。所以结果数组有了2，但因为是merge sort,所以arr3和arr5的指针还停留在1上，而arr2的指针前进到了2。结果数组为1，2。 然后我们再如法炮制，三个数组分别为
1, 2, 4
1, 3, 6
1, 5, 10

此时三个数组的指针对应的数字里，arr3的3是最小的，所以结果数组往后加一个3。arr3的指针往前走一步，到3这里。arr5的指针还停在1上。结果数组为1, 2, 3

1, 2, 4, 6
1, 3, 6, 9
1, 5, 10, 15

再比较，是arr2的指针下一个对应的数字4最小。数组往后加一个4， arr2的指针往前走一步到4，此时arr3指针停留在3，arr5对应的指针还在1上，真可怜

1, 2, 4, 6, 8
1, 3, 6, 9, 12
1, 5, 10, 15, 20
再往下走也是这样的规律。 根据上述的算法描述。我们可以得到代码如下，能过的哟：

    public int nthUglyNumber(int n) {
        int[] cache = new int[n];
        cache[0] = 1;
        ArrayList<Integer> arr2 = new ArrayList<>();
        ArrayList<Integer> arr3 = new ArrayList<>();
        ArrayList<Integer> arr5 = new ArrayList<>();
        arr2.add(1);
        arr3.add(1);
        arr5.add(1);
        int idx2 = 1, idx3 = 1, idx5 = 1;
        for (int i = 1; i < n; i++) {
            arr2.add(cache[i - 1] * 2);
            arr3.add(cache[i - 1] * 3);
            arr5.add(cache[i - 1] * 5);
            int min = Math.min(arr2.get(idx2), Math.min(arr3.get(idx3), arr5.get(idx5)));
            if (min == arr2.get(idx2)) idx2++;
            if (min == arr3.get(idx3)) idx3++;
            if (min == arr5.get(idx5)) idx5++;
            cache[i] = min;
        }
        
        return cache[n - 1];
    }

然而，其实这也不是最优的。因为其实，arr2，arr3，arr5都是结果数组乘以2，3，5得到的结果，所以根据结果数组的生成的同时更新idx2, idx3, 和idx5就行了，cache[idx2 - 1] * 2其实就是arr2.get(idx2), 同理于cache[idx3 - 1] * 3和arr3.get(idx3)，cache[idx5 - 1] * 5和arr5.get(idx5)。所以我们只需要根据cache数组和idx指针进行操作就可以了。得到代码如下

    public int nthUglyNumber(int n) {
        int[] cache = new int[n];
        cache[0] = 1;
        int idx2 = 0, idx3 = 0, idx5 = 0;
        for (int i = 1; i < n; i++) {
            int num2 = cache[idx2] * 2;
            int num3 = cache[idx3] * 3;
            int num5 = cache[idx5] * 5;
            int min = Math.min(num2, Math.min(num3, num5));
            if (min == num2) idx2++;
            if (min == num3) idx3++;
            if (min == num5) idx5++;
            cache[i] = min;
        }
        
        return cache[n - 1];
    }

看起来基本一样。但是少了三个数组的操作量。另外注意因为是cache[idx2 - 1] * 2 == 原arr2.get(idx2) 而不是 cache[idx2] * 2，所以idx2, idx3, idx5的初始值也少了1.