leetcode题目：第 k 个数

题目描述：

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

示例 1:

输入: k = 5

输出: 9

解题思路：

由题可得，数组应为3a*5b*7c，即每个数字都是列表中先前值的 3 倍、5 倍或 7 倍，因此我们可以检查所有可能的值。但要注意防止重复出现的数字。因此用动态规划DP来解决。

DP动态规划一般用三指针来实现。

举个例子
初始值 ugly[0]=1; index1=0; index2=0; index3=0

ugly[1]=Min(ugly[index1]*3,ugly[index2]*5,ugly[index3]*7)
=Min(1*3,1*5,1*7)
=3
于是 index1++;

ugly[2]=Min(ugly[index1]*3,ugly[index2]*5,ugly[index3]*7)
=Min(3*3,1*5,1*7)
=5
于是 index2++;
以此类推。

java代码实现

class Solution {
    public int getKthMagicNumber(int k) {
        int p1=0,p2=0,p3=0;
        int[] dp=new int[k];
        dp[0]=1;

        for(int i=1;i<k;i++){
            dp[i]=Math.min(Math.min(dp[p1]*3,dp[p2]*5),dp[p3]*7);
            if(dp[i]==dp[p1]*3){
                p1++;
            }
            if(dp[i]==dp[p2]*5){
                p2++;
            }
            if(dp[i]==dp[p3]*7){
                p3++;
            }
        }
        return dp[k-1];
    }
}

文章来源: blog.csdn.net，作者：小小谢先生，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/xiewenrui1996/article/details/112907488