Super Ugly Number

时间:2022-05-20 23:04:30

eg 2,3,5

把第一个元素(2,1)放到最小堆,2表示乘积,1表示乘数

       乘数     队列                          最小堆                   即将进行的操作

第一阶段  【1】   【2,3,5】                2                          (2,1)出堆,(3,1)入堆,生成新的乘数2,并且(2*2,2)入堆;

第二阶段  【1】   【3,5】                    3,4                      (3,1)出堆,(5,1)入堆,生成新的乘数3,并且(3*2,2)入堆 ;

【2】   【2,3,5】

第三阶段      【1】   【5】                        5,4,6                  (4,2)出堆,(5,1)入堆,生成新的乘数3,并且(3*2,2)入堆 ;

【2】   【2,3,5】

【3】   【2,3,5】

注意(1) 重复数据!(2)上面的队列固定,即将访问的位置是通过下标来记录的,即代码中的start_idx,记录乘数-位置之间的map关系

#include<vector>
#include<queue>
#include<map>
#include<limits>
#include<iostream>
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 nthSuperUglyNumber(int n, vector<int>& primes) {
priority_queue<Node, vector<Node>, cmp> min_heap; if(primes.size() == ) return ;
map<long , unsigned int> start_idx;//记录该乘数对应的队列访问到primes第几个元素了
start_idx[] = ;
int res = ; Node temp_node;
temp_node.idx = ; //idx is the first val of start_idx
temp_node.val = primes[];
min_heap.push(temp_node); int cnt = ;
if (n == ) return ;
long min_val;
long min_idx = ;
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] = ;
temp_node.idx = min_val; //idx is the first val of start_idx
temp_node.val = min_val * primes[];
min_heap.push(temp_node);
} if ((start_idx[min_idx] < primes.size() - ) )
{
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; }
};

Super Ugly Number的更多相关文章

  1. &lbrack;LeetCode&rsqb; Super Ugly Number 超级丑陋数

    Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose all ...

  2. Leetcode 313&period; super ugly number

    Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose all ...

  3. &lbrack;LintCode&rsqb; Super Ugly Number 超级丑陋数

    Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose all ...

  4. 313&period;&Tab;Super Ugly Number

    题目: Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose ...

  5. &lbrack;LeetCode&rsqb; Super Ugly Number &lpar;Medium&rpar;

    Super Ugly Number 最后WA没做出来. typedef long long int64; #define MAXBOUND 10000000 class Solution { publ ...

  6. Ugly Number&comma;Ugly Number II&comma;Super Ugly Number

    一.Ugly Number Write a program to check whether a given number is an ugly number. Ugly numbers are po ...

  7. &lbrack;Swift&rsqb;LeetCode313&period; 超级丑数 &vert; Super Ugly Number

    Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose all ...

  8. leetcode 263&period; Ugly Number 、264&period; Ugly Number II 、313&period; Super Ugly Number 、204&period; Count Primes

    263. Ugly Number 注意:1.小于等于0都不属于丑数 2.while循环的判断不是num >= 0, 而是能被2 .3.5整除,即能被整除才去除这些数 class Solution ...

  9. Super Ugly Number -- LeetCode

    Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose all ...

  10. &lbrack;LeetCode&rsqb; 313&period; Super Ugly Number 超级丑陋数

    Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose all ...

随机推荐

  1. Excel 自动更正

    当有复杂的字段需要重复填写怎么办呢,比如××银行卡号,××电话号码,××公司地址等.可以使用excel的"自动更正"功能解决. 1. Excel 2010的自动更正选项在哪里呢 2 ...

  2. 使用NodeList

    理解NodeList.NamedNodeMap和HTMLCollection是整体透彻理解DOM的关键. 这三个集合都是“动态”的,也就是说:每当文档结构发生变化时,他们都会得到更新,他们始终保存的都 ...

  3. AngularJS in Action读书笔记2——view和controller的那些事儿

    今天我们来818<angularjs in action>的第三章controller和view. 1.Big Picture概览图 View是angularjs编译html后呈现出来的, ...

  4. iostat命令详解

    iostat iostat用于输出CPU和磁盘I/O相关的统计信息. 命令格式: iostat [ -c | -d ] [ -k | -m ] [ -t ] [ -V ] [ -x ] [ devic ...

  5. puppet学习:类与类的依赖关系的问题

    今天在部署Zabbix的Proxy时,在负责安装的Exec中去掉了一些无关的Package的依赖,结果,就出现了依赖关系的问题. 在zabbix::install中,我写的是require mysql ...

  6. serialize

    Jquery的serialize()方法用于将表单元素转换为查询字符串格式, Submit按钮及File选择元素是不能序列化的. $('input:button').click(function() ...

  7. ubuntu 终端作死体验

    [参考]: https://blog.csdn.net/m0_37192554/article/details/81697791 https://blog.csdn.net/amazingren/ar ...

  8. &lbrack;LeetCode&rsqb; Basic Calculator IV 基本计算器之四

    Given an expression such as expression = "e + 8 - a + 5" and an evaluation map such as {&q ...

  9. c&plus;&plus;类定义代码的分离

    类文件 实际工程中,对一个类的说明.架构.描述方法是:    往往分成头文件和实现的源文件,来实现代码的分离 然后,源文件中包含类的头文件... 头文件的包含问题: 类对应的实现文件cpp.main主 ...

  10. Java实现冒泡排序、折半查找

    1.冒泡排序 public class BubbleSort{ public static void main(String[] args){ int score[] = {67, 69, 75, 8 ...