一、题目

有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21……。

二、示例

2.1> 示例 1:

【输入】 k = 5
【输出】 9

三、解题思路

其实这道题，我更强倾向于将其假设为3个马拉松选手在跑步：

A选手是以3倍基础配速来向前跑。
B选手是以5倍基础配速来向前跑。
C选手是以7倍基础配速来向前跑。

那么怎么决定每个人的基础配速是多少呢？规则就是，3个人的初始化的基础配速都是1，那么每向前跑一步，我们都选出跑出的最短距离，作为新的基础配速，并且只有每轮跑出距离最短的选手，才有资格更新自己的基础配速。

以下图为例，最初基础配速都是1，那么A选手跑出的距离是3，B选手跑出的距离是5，C选手跑出的距离是7，那么由于A选手跑出距离最短，所以增加一个基础配速“3”，然后A选手的基础配速提升为“3”；然后再继续跑，这一轮A选手跑出距离是9，B选手跑出距离是5，C选手跑出距离是7，由于B选手跑出的距离最短，所以，增加一个基础配速“5”，然后B选手的基础配速提升为“3”；以此类推……

那么最终我们根据传入的k值，来返回基础配速数组中的第k-1个基础配速值就可以了。

四、代码实现

class Solution {
    public int getKthMagicNumber(int k) {
        int index1 = 0, index2 = 0, index3 = 0;
        int[] result = new int[k];
        result[0] = 1;
        for(int i = 1; i < k; i++) {
            int minValue = Math.min(Math.min(3 * result[index1], 5 * result[index2]), 7 * result[index3]);
            if (minValue == 3 * result[index1]) index1++;
            if (minValue == 5 * result[index2]) index2++;
            if (minValue == 7 * result[index3]) index3++;
            result[i] = minValue;
        } 
        return result[k - 1];
    }
}