【动态规划专题】剑指 Offer 49. 丑数

本问题对应课程链接：剑指offer刷题第三期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi

更新于 3 年前 149 13

共以下 13 个回答

招舟子普通 2024年1月3日下午2:11

class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int a=0,b=0,c=0;
for(int i=1;i<n;i++){
dp[i] = Math.min(Math.min(dp[a]2,dp[b]3),dp[c]5);
if(dp[i]dp[a]2)a++;
if(dp[i]dp[b]3)b++;
if(dp[i]dp[c]5)c++;
}
return dp[n-1];
}
}
时间空间均是o（n）

0 赞同 0 条回复

登录以回复
九号球普通 2023年12月10日上午11:01

“`java
class Solution {
public int nthUglyNumber(int n) {
//动态规划
//dp[i]为第i个丑数，则dp[n]即为所求
//dp[1] = 1
//设置三个指针，分别对应2,3,5 ，p2,p3,p5
//i >= 2时，dp[i] = Min(dp[p2]*2,dp[p3]*3,dp[p5]*5)
//判断dp[i]与哪个相等，则对应的指针需要加1
int[] dp = new int[n + 1];
dp[1] = 1;
int p2 = 1,p3=1,p5=1;
for (int i = 2; i <= n; i++) { int p2p = dp[p2]*2; int p3p = dp[p3]*3; int p5p = dp[p5]*5; dp[i] = Math.min(Math.min(p2p, p3p),p5p); if (dp[i] == p2p) { p2++; } if (dp[i] == p3p) { p3++; } if (dp[i] == p5p) { p5++; } } return dp[n]; } }

0 赞同 0 条回复

登录以回复

张开怀普通 2023年7月24日下午5:07

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n+1, 0);
        dp[1] = 1;
        int a = 1, b = 1, c = 1;

        for(int i = 2; i <= n; i++){
            dp[i] = min(min(dp[a] * 2, dp[b] * 3), dp[c] * 5);
            if(dp[i] == dp[a] * 2) a++;
            if(dp[i] == dp[b] * 3) b++;
            if(dp[i] == dp[c] * 5) c++;
        }

        return dp[n];
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

Dsjh 普通 2023年7月23日下午6:02

MY

class Solution {
public:
    int nthUglyNumber(int n) {
        // 第n个丑数，是由前面某一个丑数*2 或者 *3 或者 *5得到
        int a=1,b=1,c=1;
        vector<int> dp(n+1,0);
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i] = min(dp[a]*2,min(dp[b]*3,dp[c]*5));
            if(dp[i] == dp[a]*2) a++;
            if(dp[i] == dp[b]*3) b++;
            if(dp[i] == dp[c]*5) c++;
        }
        return dp[n];
    }
};

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月23日上午3:26

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        a, b, c  = 1, 1, 1
        dp = [0] * (n + 1)
        dp[1] = 1

        for i in range(2, n + 1):
            dp[i] = min(dp[a] * 2, dp[b] * 3, dp[c] * 5)
            if dp[a] * 2 == dp[i]:
                a += 1
            if dp[b] * 3 == dp[i]:
                b += 1
            if dp[c] * 5 == dp[i]:
                c += 1

        return dp[n]

动态规划

0 赞同 0 条回复

BOZ 普通 2023年7月22日下午2:10

【思路】DP，dp[i]为第i个丑数
【复杂度】时间O(n)，空间O(n)

class Solution {
public:
    int nthUglyNumber(int n) {
        // dp[i] is the nth ugly number
        int *dp = new int[n];
        int prev[3] = {0};
        // begin dp
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            int min = std::min(std::min(dp[prev[0]]*2, dp[prev[1]]*3), dp[prev[2]]*5);
            if (dp[prev[0]]*2 == min) prev[0]++;
            if (dp[prev[1]]*3 == min) prev[1]++;
            if (dp[prev[2]]*5 == min) prev[2]++;
            dp[i] = min;
        }

        return dp[n - 1];
    }
};

0 赞同 0 条回复

Vow the vow。普通 2023年7月22日上午10:53

时间复杂度O(n)

public int nthUglyNumber(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        int p2 = 1,p3=1,p5=1;
        for(int i = 2; i <= n; i++){
            int num1 = dp[p2] * 2;
            int num2 = dp[p3] * 3;
            int num3 = dp[p5] * 5;
            int min = Math.min(num1, Math.min(num2,num3));
            dp[i] = min;
            if(num1 == min) p2++;
            if(num2 == min) p3++;
            if(num3 == min) p5++;
        }
        return dp[n];
    }

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月21日下午11:29

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];  // dp[i]表示第i+1个丑数
        dp[0] = 1;  // 第一个丑数是1

        int a = 0, b = 0, c = 0;    //都指向第一个

        for(int i = 1; i < n; i++){

            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;

            dp[i] = Math.min(Math.min(n2, n3), n5);

            if(dp[i] == n2){
                a++; 
            }
            if(dp[i] == n3){
                b++;
            }
            if(dp[i] == n5){
                c++; 
            }
        }

        return dp[n-1];//第n个丑数
    }
}

0 赞同 0 条回复

yxy 普通 2023年7月21日下午6:48

时间复杂度O(n)

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> v(1,1);
        int p2=0, p3=0, p5=0;
        for(int i=0;i<n-1;i++)
        {
            int next = min(2*v[p2], min(3*v[p3], 5*v[p5]));
            v.push_back(next);
            if(2*v[p2]==next) p2++;
            if(3*v[p3]==next) p3++;
            if(5*v[p5]==next) p5++;
        }
        return v.back();
    }
};

0 赞同 0 条回复

Ming 普通 2023年7月21日下午4:59
```
 public int nthUglyNumber(int n) {
        if(n <= 0) return 0;
        int[] list = new int[n];
        list[0] = 1;
        int i = 0, j = 0, k = 0;
        for(int idx = 1; idx < n; idx++) {
            int tmp = Math.min(list[i]*2, Math.min(list[j]*3, list[k]*5));
            // 三个链表可能有系统的元素，只要最小的，都要移动指针
            if(tmp == list[i] * 2) i++;
            if(tmp == list[j] * 3) j++;
            if(tmp == list[k] * 5) k++;
            list[idx] = tmp;
        }
        return list[n - 1];
    }
```
假设三个数组的指针分别是i,j,k，此时均是指向第一个元素，然后比较A[i]，B[j]和C[k]，得到的最小的数A[i]，就是ugly[1]，此时ugly就变成{1,2}了，对应的ABC数组就分别变成了：

A ： {12，22……}

B ： {13, 23……}

C ：{15,25……}

此时根据合并有序数组的原理，A数组指针i就指向了下一个元素，即’2*2’，而j和k依然分别指向B[0]和C[0]，然后进行下一轮合并，就是A[1]和B[0]和C[0]比较，最小值作为ugly[2]…..如此循环n次，就可以得到ugly[n]了。

此外，注意到ABC三个数组实际上就是ugly[]2，ugly[]3和ugly[]5的结果，所以每次只需要比较A[i]=ugly[i]2，B[j]=ugly[j]3和C[k]=ugly[k]5的大小即可。然后谁最小，就把对应的指针往后移动一个，为了去重，如果多个元素都是最小，那么这多个指针都要往后移动一个。
0 赞同 0 条回复

登录以回复

花老爷普通 2023年7月21日下午4:44

动态规划
时间：O(n)
空间：O(n)

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int f2 = 0, f3 = 0, f5 = 0;
        for (int i = 1; i < n; i++) {
            int n2 = dp[f2] * 2, n3 = dp[f3] * 3, n5 = dp[f5] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            if (dp[i] == n2) {
                f2++;
            }
            if (dp[i] == n3) {
                f3++;
            }
            if (dp[i] == n5) {
                f5++;
            }
        }
        return dp[n-1];
    }
}

0 赞同 0 条回复

怀瑾永久会员 2023年7月21日下午3:31

“`C++
int getNthUglyNumber(int n) {
vector uglyNums; // 存储丑数的数组
uglyNums.push_back(1); // 第一个丑数是1

int i2 = 0, i3 = 0, i5 = 0; // 分别用于记录下一个乘以2、3、5的丑数的索引

while (uglyNums.size() < n) {
    // 计算下一个丑数，为三个索引指向的丑数乘以对应的因子中的最小值
    int nextUglyNum = min(uglyNums[i2] * 2, min(uglyNums[i3] * 3, uglyNums[i5] * 5));
    uglyNums.push_back(nextUglyNum);

    // 更新索引
    if (nextUglyNum == uglyNums[i2] * 2) i2++;
    if (nextUglyNum == uglyNums[i3] * 3) i3++;
    if (nextUglyNum == uglyNums[i5] * 5) i5++;
}

return uglyNums.back();

}

“`

0 赞同 0 条回复

Yodl. 普通 2023年7月21日下午2:43

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0;
        int dp[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = min(min(n2, n3), n5);
            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;
        }
        return dp[n - 1];
    }
};

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【动态规划专题】剑指 Offer 49. 丑数

共以下 13 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复