Ugly Number

Med Ugly number is a number that only have factors 3, 5 and 7.

Design an algorithm to find the Kth ugly number. The first 5 ugly numbers are 3, 5, 7, 9, 15 ...

Thoughts

参考自http://bookshadow.com/weblog/2015/08/19/leetcode-ugly-number-ii/

丑陋数序列可以拆分为下面3个子列表：

(1) 1×3, 3×3, 5×3, 7×3, 9×3, …

(2) 1×5, 3×5, 5×5, 7×5, 9×5, …

(3) 1×7, 3×7, 5×7, 7×7, 9×7, …

可以发现每一个子列表都是丑陋数本身(1, 3, 5, 7, 9, …) 乘以 3, 5, 7. 因此我们可以用三个指针，分别指向三行中下个可能的数，选取其中最小的加入。

Code

    /**
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
    public long kthPrimeNumber(int k) {
        int i3 = 0, i5 = 0, i7 = 0;
        long[] res = new long[k + 1];
        res[0] = 1;
        for (int i = 1; i <= k; i++) {
            res[i] = Math.min(res[i3] * 3, Math.min(res[i5] * 5, res[i7] * 7));
            if (res[i] / res[i3] == 3) {
                i3++;
            } 
            if (res[i] / res[i5] == 5) {
                i5++;
            } 
            if (res[i] / res[i7] == 7) {
                i7++;
            }
        }

        return res[k];
    }

Analysis

光看出表还不够，还要注意里头有重复的元素。所以不能用if...else而是得三个if.

TC: O(k)