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

Have you met this question in a real interview? 

Yes

Example

If K=4, return 9.

Challenge

O(K log K) or O(K) time.

Thoughts:
http://blog.csdn.net/nisxiya/article/details/46767595


Naive solution:
Try every number and judge whether it is ugly until get the kth

Priority_queue solution:
Created a min heap and kept multiplying the minimum ugly number with 3, 5, 7 and put result into the heap. To avoid repetition, used a hashset to mark elements already in the heap
Time: O(klogk)
Space: O(k)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

class Solution { public: /* * @param k: The number k. * @return: The kth prime number as description. */ struct compNode{ bool operator()(long long a, long long b)const{ return a > b; } }; long long kthPrimeNumber(int k) { priority_queue<long long, vector<long long>, compNode> pq; long long cur; //vector<int> res; unordered_set<long long> hashset; pq.push(1); for(int i = 0; i <= k; i++){ cur = pq.top(); pq.pop(); if(!hashset.count(cur * 3)) { pq.push(cur * 3); hashset.insert(cur * 3); } if(!hashset.count(cur * 5)){ pq.push(cur * 5); hashset.insert(cur * 5); } if(!hashset.count(cur * 7)){ pq.push(cur * 7); hashset.insert(cur * 7); } } return cur; } };

Normal Solution:
Thought: http://www.cnblogs.com/EdwardLiu/p/4322664.html
Generate ugly number through competition:
Time: O(n)
Space: O(n)
There are repeatations like 15 = 3 * 5 = 5 * 3, in this case, the i3 and i5 will proceed at the same time. So no repetations in result array.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

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