本文共 1415 字，大约阅读时间需要 4 分钟。
注意负数，所以要使用long，而不能用int
详细解释 请参见http://www.cnblogs.com/julie-yang/p/5147460.html
#include #include #include #include #include using namespace std;struct Node{ long idx; long val;};struct cmp{ bool operator()(const Node &a,const Node &b) { return a.val>b.val; }};class Solution {public: int nthUglyNumber(int n) { priority_queue , cmp> min_heap; vector primes; primes.push_back(2); primes.push_back(3); primes.push_back(5); if (primes.size() == 0) return 0; map start_idx; start_idx[1] = 0; int res = 1; Node temp_node; temp_node.idx = 1; //idx is the first val of start_idx temp_node.val = primes[0]; min_heap.push(temp_node); int cnt = 1; if (n == 1) return 1; long min_val = INT_MAX; long min_idx = 0; while (cnt < n) { min_val = min_heap.top().val; min_idx = min_heap.top().idx; min_heap.pop(); if ((res != (min_val))) { res = min_val; cnt++; start_idx[min_val] = 0; temp_node.idx = min_val; //idx is the first val of start_idx temp_node.val = min_val * primes[0]; min_heap.push(temp_node); } if (start_idx[min_idx] < primes.size() - 1) { start_idx[min_idx] ++; temp_node.idx = min_idx; //idx is the first val of start_idx temp_node.val = min_idx * primes[start_idx[min_idx]]; min_heap.push(temp_node); } } return res; }};
转载于:https://www.cnblogs.com/julie-yang/p/5147485.html