北碚网站建设公司/seo页面如何优化
*/
两种方法：
方法一：
/**
* 思路：将列表中的数字与3,5,7相乘，找出还未加入列表的最小数。
* 每次要将Ai加入列表时，就用某个临时列表存放3Ai，5Ai和7Ai。要产生Ai+1时，搜索临时列表，找出最小值。
* @param k
* @return
*/
public static int getKthMagicNumger(int k){
if(k<0)
return 0;
int val=1;
Queue q=new LinkedList();
addProducts(q,1);
for(int i=0;i
val=removeMin(q);
addProducts(q,val);
}
return val;
}
public static void addProducts(Queue q,int v){
q.add(v*3);
q.add(v*5);
q.add(v*7);
}
//取出最小值
public static int removeMin(Queue q){
int min=q.peek();
for(Integer v:q){
if(v
min=v;
}
}
while(q.contains(min)){
q.remove(min);
}
return min;
}
方法二：
/**
* 思路：(优化)从一开始就按常数因子将列表分组存放，那就只需检查3,5,和7倍数的第一个，后续元素一定比第一个大。
* 当这些元素在其他列表中不存在是，将其插入列表。
* 伪代码如下：
* 1)初始化array和队列：Q3，Q5和Q7。
* 2)将1插入array.
* 3)分别将1*3,1*5,1*7插入Q3，Q5和Q7。
* 4)令x为Q3，Q5和Q7中的最小值。将x添加至array尾部。
* 5)若x存在于：
* Q3：将x*3，x*5,x*7放入Q3，Q5和Q7，从Q3中移除x。
* Q5：将x*5,x*7放入Q5和Q7，从Q5中移除x。
* Q7: 将x*7放入Q7，从Q7中移除x。
* 6)重复4~6，直到找到第k个元素。
* @param k
* @return
*/
public static int getKthMagitNumber2(int k){
if(k<0)
return 0;
int val=1;
Queue queue3=new LinkedList();
Queue queue5=new LinkedList();
Queue queue7=new LinkedList();
queue3.add(1);
for(int i=0;i
int v3=queue3.size()>0?queue3.peek():Integer.MAX_VALUE;
int v5=queue5.size()>0?queue5.peek():Integer.MAX_VALUE;
int v7=queue7.size()>0?queue7.peek():Integer.MAX_VALUE;
val=Math.min(v3, Math.min(v5, v7));
if(val==v3){
queue3.remove();
queue3.add(val*3);
queue5.add(val*5);
}else if(val==v7){
queue5.remove();
queue5.add(val*5);
}else if(val==v7){
queue7.remove();
}
queue7.add(val*7);
}
return val;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
原文：http://blog.csdn.net/shangqing1123/article/details/47357593