问题描述
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 …
问题分析
这个题，有多种方法求解，常见的是有辅助数据结构，比如priority_queue，或是常说的最大最小堆也可。
解法一：时间复杂度O(k log k)，空间复杂度O(k)使用priority_queue模拟最小堆： priority_queue<int, vector<int>, greater<int> >. 从中取出最小的 ugly number , 然后该 ugly number 分别乘以3, 5, 7 然后又放进 priority_queue中如果上述过程中，将乘以3,5,7之后的数直接放入 priority_queue 将可能导致重复放入的问题，比如：当取出 9， 然后放入27, 45, 63,。后面当取出 21 时，放入 63, 105, 147，，这里就重复放入 63 了。因此需要用个 unordered_set<int> 来 mark 哪些元素已经放入过了。
时间复杂度分析：共 k 个元素，每次取出一个元素时，都需要对堆进行操作，时间复杂度为 O(k)，因此时间复杂度为 O(k log k).
解法二：时间复杂度 O(k)，空间复杂度O(k)使用 primes 数组来记录前 k 个ugly_number。在生成 primes 数组时，新增入的元素，肯定是该 primes 数组中前面某些元素乘以3，或是乘以5，或是乘以7的结果，且是最小的。依据此思想，可以构建如下的代码class Solution {public:/** @param k: The number k.* @return: The kth prime number as description.*/long long kthPrimeNumber(int k) {> primes(k+1);primes[0] = 1;int i3 = 0, i5 = 0, i7 = 0;for (int i = 1; i <= k; i++) {long long nextPrime = min( min(primes[i3]*3, primes[i5]*5), primes[i7]*7 );if (nextPrime == primes[i3]*3) i3++;if (nextPrime == primes[i5]*5) i5++;if (nextPrime == primes[i7]*7) i7++;primes[i] = nextPrime;}return primes[k];}};
复杂度分析：现在只需要进行 k 次操作，每次操作耗时是 O(1)，因此总的时间复杂度是 O(k)，而总的时间复杂度是 O(k)。
这里的风景美不胜收，真让人流连忘返。
