一道微软面试题的java解法(2)
/*
* 一个有序数列，序列中的每一个值都能够被2或者3或者5所整除，
* 1是这个序列的第一个元素。求第1500个值是多少？
* 这道题目当时面试的时候用了一个很笨的方法。真的很糗。呵呵！：）
* 这个类用来计算这个序列的第n个元素的值。
*
*/
package bia.arithmetic;
import java.util.Date;
/**
* @author Renzhichao
*/
public class NextItem {
/**
*
*/
public NextItem() {
super();
// TODO Auto-generated constructor stub
array[0] = 1;
posX = 0;
posY = 0;
posZ = 0;
itemPos = 0;
cal();
}
void cal() {
valX = 2 * array[posX];
valY = 3 * array[posY];
valZ = 5 * array[posZ];
}
long array[] = new long[1500];
int posX, posY, posZ;
long valX, valY, valZ;
int itemPos;
/**
* 计算序列中的下一个元素
* @Renzhichao
*
*/
public void nextItem() {
long min = valX;
boolean flagX = false ;
boolean flagY = false ;
boolean flagZ = false ;
if (valY < min) {
min = valY;
}
if (valZ < min) {
min = valZ;
}
if (min==valX){
flagX = true ;
}
if (min==valY){
flagY = true ;
}
if (min==valZ){
flagZ = true ;
}
if (min > array[itemPos]) {
itemPos++;
array[itemPos] = min ;
if (flagX) posX++ ;
if (flagY) posY++ ;
if (flagZ) posZ++ ;
}
cal() ;
}
/**
* 得到这个序列中的第n个元素
* @Renzhichao
* @param no
* @return
*/
public long getItem(int no){
for (int i = 0; i < (no-1); i++) {
nextItem() ;
}
return array[itemPos] ;
}
public static void main(String[] args) {
NextItem ins = new NextItem() ;
long first = new Date().getTime() ;
System.out.println("The 1500th Item is "+ins.getItem(1500));
System.out.println("THe Cost of time is :"+(new Date().getTime()-first)+"ms");
}
}