Ugly Number

Source

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 ...

Example
If K=4, return 9.
Challenge
O(K log K) or O(K) time.      

題解1

尋找第 K 個醜數，醜數在這裡的定義是僅能被3，5，7整除。簡單粗暴的方法就是挨個檢查正整數，數到第 K 個醜數時即停止。

Java

class Solution {
    /**
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
    public long kthPrimeNumber(int k) {
        if (k <= 0) return -1;

        int count = 0;
        long num = 1;
        while (count < k) {
            num++;
            if (isUgly(num)) {
                count++;
            }
        }

        return num;
    }

    private boolean isUgly(long num) {
        while (num % 3 == 0) {
            num /= 3;
        }
        while (num % 5 == 0) {
            num /= 5;
        }
        while (num % 7 == 0) {
            num /= 7;
        }

        return num == 1;
    }
}      

源碼分析

判斷醜數時依次約掉質因數3，5，7，若處理完所有質因數3，5，7後不為1則不是醜數。自增 num 時應在判斷是否為醜數之前。

複雜度分析

無法準确分析，但是估計在 O(n^3) 以上。

題解2 - 二分查找

根據醜數的定義，它的質因數隻含有3, 5, 7, 那麼根據這一點其實可以知道後面的醜數一定可以從前面的醜數乘3,5,7得到。那麼可不可以将其遞推關系用數學公式表示出來呢？

我大概做了下嘗試，首先根據醜數的定義可以寫成 Uk=3^x3⋅5^x5⋅7^x7, 那麼 Uk+1 和 Uk 的不同則在于 x3,x5,x7 的不同，遞推關系為 Uk+1=Uk⋅[(3^z3⋅5^z5⋅7^z7)/(3^y3⋅5^y5⋅7^y7)],将這些分數按照從小到大的順序排列可在 O(K) 的時間内解決，但是問題來了，得到這些具體的 y,zy, zy,z 就需要費不少時間，且人工操作極易漏解。:( 是以這種解法隻具有數學意義，沒有想到好的實作方法。

除了這種找相鄰遞推關系的方法我們還可以嘗試對前面的醜數依次乘3, 5, 7，直至找到比目前最大的醜數大的一個數，對乘積後的三種不同結果取最小值即可得下一個最大的醜數。這種方法需要儲存之前的 N 個醜數，由于已按順序排好，天然的二分法。

C++

class Solution {
public:
    /*
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
    long long kthPrimeNumber(int k) {
        if (k <= 0) return -1;

        vector<long long> ugly(k + 1);
        ugly[0] = 1;
        int index = 0, index3 = 0, index5 = 0, index7 = 0;
        while (index <= k) {
            long long val = ugly[index3]*3 < ugly[index5]*5 ? ugly[index3]*3 : ugly[index5]*5;
            val = val < ugly[index7]*7 ? val : ugly[index7]*7;
            if (val == ugly[index3]*3) ++index3;
            if (val == ugly[index5]*5) ++index5;
            if (val == ugly[index7]*7) ++index7;
            ugly[++index] = val;
        }
        return ugly[k];
    }
};      

class Solution {
    /**
     * @param k: The number k.
     * @return: The kth prime number as description.
     */
    public long kthPrimeNumber(int k) {
        if (k <= 0) return -1;

        ArrayList<Long> nums = new ArrayList<Long>();
        nums.add(1L);
        for (int i = 0; i < k; i++) {
            long minNextUgly = Math.min(nextUgly(nums, 3), nextUgly(nums, 5));
            minNextUgly = Math.min(minNextUgly, nextUgly(nums, 7));
            nums.add(minNextUgly);
        }

        return nums.get(nums.size() - 1);
    }

    private long nextUgly(ArrayList<Long> nums, int factor) {
        int size = nums.size();
        int start = 0, end = size - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums.get(mid) * factor > nums.get(size - 1)) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (nums.get(start) * factor > nums.get(size - 1)) {
            return nums.get(start) * factor;
        }

        return nums.get(end) * factor;
    }
}