一道微软面试题的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");
 }
}

本文地址：http://com.8s8s.com/it/it17897.htm