264. Ugly Number II

    /*
     * 264. Ugly Number II 
     * 2016-6-22 by Mingyang
     * http://www.cnblogs.com/Liok3187/p/4751127.html
     * 这道题目略抽象，自己慢慢体会
     * 注意的是idx++并不代表乘以2，3，5的基数，而是uglyNumber数组的第idx个值
     * 其实吧，这个题目就相当于2，3，5三个相互竞争，不过前提是都要乘以uglyNumber的数，不能乘以7以保证纯粹
     * 那么有这么一条规矩，开始的都是都从第一个uglyNumber走，如果2中标以后，2的index要加加，为了平衡游戏
     * 不然2会一直中标下去，其他对手没的玩，那么2接下来就要乘以第二个更大的数，这样3才能找到优势拿下第二个
     * 这个题目的原理就是通过前面的uglyNumber来不断的构造后面的uglyNumber
     * An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
     */
     public int nthUglyNumber(int n) {
            int[] uglyNumbers = new int[n];
            uglyNumbers[0] = 1;
            int idx2 = 0;
            int idx3 = 0;
            int idx5 = 0;
            int counter = 1;
            while (counter < n) {
                int min = Math.min(Math.min(
                    uglyNumbers[idx2] * 2, 
                    uglyNumbers[idx3] * 3),
                    uglyNumbers[idx5] * 5);
                if (min == uglyNumbers[idx2] * 2) {
                    idx2++;
                }
                if (min == uglyNumbers[idx3] * 3) {
                    idx3++;
                }
                if (min == uglyNumbers[idx5] * 5) {
                    idx5++;
                }
                uglyNumbers[counter] = min;
                counter++;
            }
            return uglyNumbers[n - 1];
        }