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() == 0) return 0; map<long , unsigned int> start_idx;//记录该乘数对应的队列访问到primes第几个元素了 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; 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; } };