0313super_ugly_number

本文主要是介绍0313super_ugly_number，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

0313超级丑数

题目

https://leetcode-cn.com/problems/super-ugly-number/

方法一：最小堆

class Solution {
public:int nthSuperUglyNumber(int n, vector<int>& primes) {//使用优先队列来构建最小堆，依次取出最小堆的堆顶元素，取n次priority_queue<long,vector<long>,greater<long>> heap;//定义数组记录第n个数set<long> seen;heap.push(1);seen.insert(1);long cur=0;for(int i=0;i<n;i++){cur=heap.top();heap.pop();for(long j:primes){long flag=j*cur;//如果成功插入到set中，就把seen加入到堆里面if(seen.insert(flag).second)heap.push(flag);}}return (int)cur;}
};

priority_queue

• 定义了一个元素有序排列的队列。默认队列头部的元素优先级最高。因为它是一个队列，所以只能访问第一个元素，这也意味着优先级最高的元素总是第一个被处理

• 模板有 3 个参数，其中两个有默认的参数；第一个参数是存储对象的类型，第二个参数是存储元素的底层容器，第三个参数是函数对象，它定义了一个用来决定元素顺序的断言

  template <typename T, typename Container=std::vector<T>, typename Compare=std::less<T>> class priority_queue
  

  //最大堆的定义
  priority_queue <int,vector<int>,less<int> > p;
  //最小堆定义
  priority_queue <int,vector<int>,greater<int> > q;
  

• push(const T& obj)：将obj的副本放到容器的适当位置，这通常会包含一个排序操作。

  pop()：移除第一个元素。

  top()：返回优先级队列中第一个元素的引用。

set

• insert(key_value);

  将key_value插入到set中 ，返回值是pair<set::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key_value已经在set中，则iterator表示的key_value在set中的位置。

这篇关于0313super_ugly_number的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---