第k个数

原创
2016/08/15 19:16
阅读数 476
  • 有一些数的素因子只有3、5、7,请设计一个算法,找出其中的第k个数。给定一个数int k,请返回第k个数。保证k小于等于100。
  • 测试样例:3 返回:7
import java.util.*;
public class KthNumber {
    public int findKth(int k) {
        int val = 1;
        LinkedList<Integer> list3 = new LinkedList<>();
        LinkedList<Integer> list5 = new LinkedList<>();
        LinkedList<Integer> list7 = new LinkedList<>();
        list3.push(1);
        int val3, val5, val7;
        while(k-- >= 0){
            val3 = !list3.isEmpty() ? list3.peek() : Integer.MAX_VALUE;
            val5 = !list5.isEmpty() ? list5.peek() : Integer.MAX_VALUE;
            val7 = !list7.isEmpty() ? list7.peek() : Integer.MAX_VALUE;
            val = Math.min(Math.min(val3, val5), val7);
            if(val == val3){
                list3.pop();
                list3.addLast(val * 3);
                list5.addLast(val * 5);
                list7.addLast(val * 7);
            }else if(val == val5){ //递增的目的是小的已经被前面的找到过了
                list5.pop();
                list5.addLast(val * 5);
                list7.addLast(val * 7);
            }else{
                list7.pop();
                list7.addLast(val * 7);
            }

        }
        return val;
    }

}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部