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。算法描述如下：

. 初始化结果res=1和队列q3,q5,q7
. 分别往q3,q5,q7插入1*,*,*
. 求出三个队列的队头元素中最小的那个x，更新结果res=x
. 如果x在：
q3中，那么从q3中移除x，并向q3，q5，q7插入3*x,*x,*x
q5中，那么从q5中移除x，并向q5，q7插入5*x,*x
q7中，那么从q7中移除x，并向q7插入7*x
. 重复步骤3－，直到找到第k个满足条件的数

注意，当x出现在q5中，我们没往q3中插入3*x，那是因为这个数在q5中已经插入过了。

C++实现代码：

#include<iostream>
#include<queue>
using namespace std;int get_num(int k)
{
if(k<=)
return ;
int res,cnt=;
queue<int> q3,q5,q7;
q3.push();
q5.push();
q7.push();
while(cnt<k)
{
res=min(q3.front(),min(q5.front(),q7.front()));
if(res==q3.front())
{
q3.pop();
q3.push(*res);
q5.push(*res);
q7.push(*res);
}
else if(res==q5.front())
{
q5.pop();
q5.push(*res);
q7.push(*res);
}
else if(res==q7.front())
{
q7.pop();
q7.push(*res);
}
cnt++;
}
return res;
}int main()
{
cout<<get_num()<<endl;
}