题解 | #丑数#

丑数

http://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        int factors[] = {2, 3, 5};
        unordered_set<long> hash; // 哈希表防止有重复数进入
        priority_queue<long,vector<long>, greater<long>> heap; // 小顶堆输出第n个丑叔
        hash.insert(1);
        heap.push(1);
        int ugly = 0;
        for(int i = 0; i < index; i++) {
            int cur = heap.top();
            heap.pop();
            ugly = (int)cur;
            for(auto factor:factors) {
                long x = cur * factor;
                if(!hash.count(x)){
                    hash.insert(x);
                    heap.push(x);
                }
            }
        }
        return ugly;
    }
};
全部评论

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
仁者伍敌:牛子这些人还会点一个自动回复,boss都不带回复的
点赞 评论 收藏
分享
07-01 17:14
中北大学 Java
兄弟们是真是假
牛客46374834...:我在boss上投java岗从来没成功过
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务