首页 > 代码库 > careercup-数学与概率 7.7
careercup-数学与概率 7.7
7.7 有些数的素因子只有3、5、7,请设计一个算法,找出其中第k个数。
解法:
首先,我们可以将满足条件的前几个数列出来,以此寻找解题思路。
一种简单的思路就是对于已经列出的数,我们依次去乘以3,5,7得到一组数 然后找出最小且还没有列出的数,加入到这个列表。然后重复上面的步骤: 乘以3,5,7,找出最小且还没有列出的数……这个方法的时间复杂度是O(n2 )。
这种思路存在一个问题,就是重复计算。比如对于上面那个表,我想计算下一个数, 那么我用3,5,7去乘以表中的每一个数,然后找出最小且没有用过的数。 可是像3*3,3*5,3*7,5*5,5*7
等等都是已经计算过且已经用了的, 按照上面的算法就会不断地重复计算。那我们有没什么办法可以避免重复计算呢? 那就是将已经计算出来的数保存好,并且保持它们有序。为了避免出现先用3乘以5, 然后又用5去乘以3的这种情况出现(这样会使我们维护的数中出现重复), 我们可以用3个队列来维护这些数。第1个队列负责乘以3,第2个队列负责乘以5, 第3个队列负责乘以7。算法描述如下:
1. 初始化结果res=1和队列q3,q5,q72. 分别往q3,q5,q7插入1*3,1*5,1*73. 求出三个队列的队头元素中最小的那个x,更新结果res=x4. 如果x在: q3中,那么从q3中移除x,并向q3,q5,q7插入3*x,5*x,7*x q5中,那么从q5中移除x,并向q5,q7插入5*x,7*x q7中,那么从q7中移除x,并向q7插入7*x5. 重复步骤3-5,直到找到第k个满足条件的数
注意,当x出现在q5中,我们没往q3中插入3*x,那是因为这个数在q5中已经插入过了。
C++实现代码:
#include<iostream>#include<queue>using namespace std;int get_num(int k){ if(k<=0) return 0; int res,cnt=1; queue<int> q3,q5,q7; q3.push(3); q5.push(5); q7.push(7); while(cnt<k) { res=min(q3.front(),min(q5.front(),q7.front())); if(res==q3.front()) { q3.pop(); q3.push(3*res); q5.push(5*res); q7.push(7*res); } else if(res==q5.front()) { q5.pop(); q5.push(5*res); q7.push(7*res); } else if(res==q7.front()) { q7.pop(); q7.push(7*res); } cnt++; } return res;}int main(){ cout<<get_num(10)<<endl;}
careercup-数学与概率 7.7
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。