题解 | #丑数#
丑数
https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b
#include <queue> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param index int整型 * @return int整型 */ int GetUglyNumber_Solution(int index) { // write code here //排除0 if (index == 0 ) { return 0; } priority_queue<long, vector<long>, greater<long>> pq; unordered_set<long> uset; pq.push(1); int i = 0; uset.insert(1); vector<int> prim = {2, 3, 5}; long top_value = 0; while ( i < index ) { top_value = pq.top(); pq.pop(); i++; for (auto num : prim) { int tem = num * top_value; if (uset.count(tem) != 0) { continue; } else { uset.insert(tem); pq.push(num * top_value); } } } return top_value; } };
如果x是丑数,则2x, 3x, 5x均是丑数。