Ugly Number · 數據結構與算法/leetcode/lintcode題解

# Ugly Number ### Source - leetcode: [Ugly Number | LeetCode OJ](https://leetcode.com/problems/ugly-number/) - lintcode: [(4) Ugly Number](http://www.lintcode.com/en/problem/ugly-number/) ~~~ 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 - [TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。") Lintcode 和 Leetcode 中質數稍微有點區別，這里以 Lintcode 上的版本為例進行說明。尋找第 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(n3)O(n^3)O(n3) 以上。 ### 題解2 - 二分查找根據丑數的定義，它的質因數只含有3, 5, 7, 那么根據這一點其實可以知道后面的丑數一定可以從前面的丑數乘3,5,7得到。那么可不可以將其遞推關系用數學公式表示出來呢？我大概做了下嘗試，首先根據丑數的定義可以寫成 Uk=3x3?5x5?7x7U_k = 3^{x_3} \cdot 5^{x_5} \cdot 7^{x_7}Uk=3x3?5x5?7x7, 那么 Uk+1U_{k+1}Uk+1 和 UkU_kUk 的不同則在于 x3,x5,x7x_3, x_5, x_7x3,x5,x7 的不同，遞推關系為 Uk+1=Uk?3y3?5y5?7y73z3?5z5?7z7U_{k+1} = U_k \cdot \frac{3^{y_3} \cdot 5^{y_5} \cdot 7^{y_7}}{3^{z_3} \cdot 5^{z_5} \cdot 7^{z_7}}Uk+1=Uk?3z3?5z5?7z73y3?5y5?7y7,將這些分數按照從小到大的順序排列可在 O(K)O(K)O(K) 的時間內解決，但是問題來了，得到這些具體的 y,zy, zy,z 就需要費不少時間，且人工操作極易漏解。:( 所以這種解法只具有數學意義，沒有想到好的實現方法。除了這種找相鄰遞推關系的方法我們還可以嘗試對前面的丑數依次乘3, 5, 7，直至找到比當前最大的丑數大的一個數，對乘積后的三種不同結果取最小值即可得下一個最大的丑數。這種方法需要保存之前的 N 個丑數，由于已按順序排好，天然的二分法。 ### 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; 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; } } ~~~ ### 源碼分析 `nextUgly`根據輸入的丑數數組和 factor 決定下一個丑數，`nums.add(1L)`中1后面需要加 L表示 Long, 否則編譯錯誤。 ### 復雜度分析找下一個丑數 O(logK)O(\log K)O(logK), 循環 K 次，故總的時間復雜度近似 O(KlogK)O(K \log K)O(KlogK), 使用了數組保存丑數，空間復雜度 O(K)O(K)O(K). ### 題解3 - 動態規劃 TBD ### Reference - 《劍指 Offer》第五章 - [Ugly Numbers - GeeksforGeeks](http://www.geeksforgeeks.org/ugly-numbers/)