赞
踩
超级丑数 是一个正整数,并满足其所有质因数都出现在质数数组 primes 中。
给你一个整数 n 和一个整数数组 primes ,返回第 n 个 超级丑数 。
题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。
示例 1:
输入:n = 12, primes = [2,7,13,19]
输出:32
解释:给定长度为 4 的质数数组 primes = [2,7,13,19],前 12 个超级丑数序列为:[1,2,4,7,8,13,14,16,19,26,28,32] 。
示例 2:
输入:n = 1, primes = [2,3,5]
输出:1
解释:1 不含质因数,因此它的所有质因数都在质数数组 primes = [2,3,5] 中。
问 答 什么是超级丑数? 所有质因数都出现在质数数组 primes
.怎么获得超级丑数? primes
数组里的数去相乘得到的数就睡超级丑数.怎么获取小的超级丑数? 用小根堆来存储每一次获得的超级丑数,这样每次都能获得最小的. 再用最小的超级丑数去乘以序列中的值
,获得超级丑数.怎么判断最小的超级丑数是否重复? 用哈希表来存储已经出现过的超级丑数 什么时候结束? 当获取到n个超级丑数,返回最小堆的最顶值即可.
- 思路已经有了,就是每次都用最小的超级丑数(第一个一定为1),乘以序列压小根堆.循环n-1次即可
class Solution { public: int nthSuperUglyNumber(int n, vector<int>& primes) { //哈希表来存储已经出现过的超级丑数 set<int>hash; //小根堆来获取每一轮中最小的超级丑数 priority_queue<int, vector<int>, greater<int>> que; //第一个一定为1 que.push(1); //减去一个1,因为第一个值为1 n--; //直到n为0就循环了n次. while (n--) { //获取最小的超级丑数 int index = que.top(); //最小丑数出栈 que.pop(); //用超级丑数去乘剩下的质数,获取后面的超级丑数 for (const int num : primes) { //如果超出了INT_MAX,就不需要继续了 if (index > INT_MAX/num) break; //如果这个超级丑数还没用被遍历过 if (hash.find(num * index) == hash.end()) { //压入小根堆 que.push(num * index); //哈希表更新 hash.emplace(num * index); } } } //返回当前的堆顶 return que.top(); } };
上面的做法中,我们是每个超级丑数都循环乘一遍序列.可是这样有很多数会重复,.而且很多值也基本用不到,所以就造成了很多值都是不需要去遍历的,那有没用一种方法来用最少的步骤获取最小的超级丑数.
问 答 怎么减少次数? 可以记录当前值的下标,然后超级丑数出堆的时候循环到下标的所指向的值即可
.(减少重复的值)
- 就比如[2,7,9,13],我们用小根堆存储的样式为{{2,0},{7,1},{9,2},{13,3}}.
- 当前的最小丑数是2,那么2出堆之后就会只乘
primes[0]
不需要去乘其它的数.然后重新压入{4,0}
.- 这样如果到最小丑数为7时,对应的小标为1.那么我们需要压入的有
{14,0},{49,1}
;- 循环n次即可,这样可以确保不重复的同时又不会错过最小的超级丑数.
class Solution { public: typedef pair<int, int> pii; int nthSuperUglyNumber(int n, vector<int>& primes) { if (n == 1) return 1; //定义一个小根堆,用pair来存储数据 priority_queue<pii, vector<pii>, greater<pii>> que; //超级丑数序列先压入小根堆中 for (int i = 0; i < primes.size(); ++i) que.emplace(primes[i], i); //1为超级丑数,不需要再遍历了.直接减去 n--; //获取每个超级丑数的值 int res = 0; //下标 int index = 0; //循环n次 while (n) { //获得最小的超级丑数的值和下标 res = que.top().first; index = que.top().second; que.pop(); //只循环下标的次数,压入获得的超级丑数即可 for (int i = 0; i <= index; ++i) { que.emplace(res * primes[i], i); } --n; } //最后一次的res就是结果 return res; } };
这道题如果用第一种并不难做,难点在于怎么去减少循环的次数.有很多数是不需要计算的,而且有很多是重复的,所以并不需要每一个超级丑数都要去乘以序列.
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。