第k个数

import java.util.*;

public class KthNumber {
    public int findKth(int k) {
        // write code here
    	int[] res = new int[101];
    	
    	res[0] = 1;
    	int p3 = 0;
    	int p5 = 0;
    	int p7 = 0;
    	int min = 0;
    	
    	for (int i = 1; i <= k; i++) {
    		min  = res[p3] * 3;
    		
    		if (min > res[p3] * 3) {
    			min = res[p3] * 3;
    		}
    		
    		if (min > res[p5] * 5) {
    			min = res[p5] * 5;
    		}
    		
    		if (min > res[p7] * 7) {
    			min = res[p7] * 7;
    		}
    		
    		res[i] = min;
    		
    		if (min % 3 == 0) {
    			p3++;
    		}
    		
    		if (min % 5 == 0) {
    			p5++;
    		}
    		
    		if (min % 7 == 0) {
    			p7++;
    		}
    	}
    	
    	return res[k];
    }
}

思路来自于剑指offer。下一个（大于第3个数之后）满足条件的数一定是前面的某个数乘以3，或者5，或者7得到的。
采用三个索引index3, index5, index7来记录乘以3，乘以5，乘以7：index3索引的位置满足条件，index3位置的数乘以3之后刚好大于当前的数，
对于index5和index7同理。

public class KthNumber {
    public int findKth(int k) {
        if(k == 1) return 3;
        if(k == 2) return 5;
        if(k == 3) return 7;
        List<Integer> list = new ArrayList<>();
        list.add(3);
        list.add(5);
        list.add(7);
        int index3 = 0, index5 = 0, index7 = 0;
        for(int i = 4; i <= k; i++) {
            int tmp3 = list.get(index3) * 3;
            int tmp5 = list.get(index5) * 5;
            int tmp7 = list.get(index7) * 7;
            int min = tmp3 < tmp5 ? tmp3 : tmp5;
            min = min < tmp7 ? min : tmp7;
            list.add(min);
            //更新索引的位置
            while(list.get(index3) * 3 <= min) {
                index3++;
            }
            while(list.get(index5) * 5 <= min) {
                index5++;
            }
            while(list.get(index7) * 7 <= min) {
                index7++;
            }
        }
        return list.get(k - 1);
    }
}

    public boolean isok(int i){
		while(i!=1){
			if(i%3==0)
				i /= 3;
			else if(i%5==0)
				i /= 5;
			else if(i%7==0)
				i /= 7;
			else 
				return false;
		}
		
		return true;
	}
	
	public int findKth(int k) {
        // write code here
		int ans = 0;
		int no = 0;
		for(int i=3;i<50000;i++){
			if(isok(i)){
				no++;
				if(no==k){
					ans = i;
					break;
				}
			}
		}
		
		return ans;
    }

}

思路

1. 使用三个队列q2、q3、q5，最初存放2、3、5；
2. 取出队首最小的值： 2.1. 若从q2中取出，则分别X2、X3、X5，分别添加至q2、q3、q5的末尾； 2.2. 若从q3中取出，则分别X3、X5，分别添加至q3、q5的末尾； 2.3. 若从q5中取出，则分别X5，分别添加至q5的末尾；

代码

public int findKth(int k) {
    LinkedList<Integer> q3 = new LinkedList<>();
    LinkedList<Integer> q5 = new LinkedList<>();
    LinkedList<Integer> q7 = new LinkedList<>();
    q3.offer(3);
    q5.offer(5);
    q7.offer(7);

    int index = 1;
    int min = 0;
    while( index<=k ){
        min = Math.min(q3.peek(), Math.min(q5.peek(), q7.peek()));
        if ( min==q3.peek() ) {
            q3.poll();
            q3.offer(min*3);
            q5.offer(min*5);
            q7.offer(min*7);
        }
        if ( min==q5.peek() ) {
            q5.poll();
            q5.offer(min*5);
            q7.offer(min*7);
        }
        if ( min==q7.peek() ) {
            q7.poll();
            q7.offer(min*7);
        }
        index++;
    }

    return min;
}

//类似丑数的解法，只是转而求第k+1个，默认第一个数为1，以便计算

public static int findKth(int k) {
	int kthIndex = k + 1;
	int[] numbers = new int[kthIndex];
	numbers[0] = 1;
	int nextIndex = 1;

	int i3 = 0;
	int i5 = 0;
	int i7 = 0;

	while (nextIndex < kthIndex) {
	    int multiply3 = numbers[i3] * 3;
	    int multiply5 = numbers[i5] * 5;
	    int multiply7 = numbers[i7] * 7;
	    int min = (multiply3 < multiply5) ? multiply3 : multiply5;
	    min = (min < multiply7) ? min : multiply7;

	    numbers[nextIndex] = min;

	    if (min == multiply3) {
		 i3++;
	    }
	    if (min == multiply5) {
		 i5++;
	    }
	    if (min == multiply7) {
		 i7++;
	    }

	    nextIndex++;
	}

	int kthN = numbers[nextIndex-1];
	return kthN;

    }