⭐️前面的话⭐️

️坚持和努力一定能换来诗与远方！

# ⭐️剑指 Offer 49. 丑数⭐️

## 题目详情

输入: n = 10



1. 1 是丑数。
2. n 不超过1690。

## 解题思路

u g l y [ n ] = m i n { n a , n b , n c } ugly[n] = min\{na, nb, nc\} ugly[n]=min{ na,nb,nc}
{ n a = u g l y [ a ] ∗ 2 n b = u g l y [ b ] ∗ 3 n c = u g l y [ c ] ∗ 5 , a , b , c < n \left\{ \begin{array}{c} na = ugly[a] ∗ 2 \\ nb = ugly[b] ∗ 3 \\ nc = ugly[c] ∗ 5 \end{array} \right. ,a,b,c < n na=ugly[a]2nb=ugly[b]3nc=ugly[c]5,a,b,c<n

## 源代码

C语言：

int min(int x, int y, int z)
{
int m = 0;
m = x < y ? x : y;
m = m < z ? m : z;
return m;
}
int nthUglyNumber(int n){
int a = 0;
int b = 0;
int c = 0;
int* ugly = (int*)malloc(sizeof(int) * n);
int i = 0;
ugly[0] = 1;
for (i = 1; i < n; i++)
{
int na = ugly[a] * 2;
int nb = ugly[b] * 3;
int nc = ugly[c] * 5;
ugly[i] = min(na, nb, nc);
if (ugly[i] == na)
a++;
if (ugly[i] == nb)
b++;
if (ugly[i] == nc)
c++;
}
return ugly[n - 1];
}


Java语言：

class Solution {
public int nthUglyNumber(int n) {
int a = 0;
int b = 0;
int c = 0;
int[] ugly = new int[n];
int i = 0;
ugly[0] = 1;
for (i = 1; i < n; i++) {
int na = ugly[a] * 2;
int nb = ugly[b] * 3;
int nc = ugly[c] * 5;

int min = Math.min(na, nb);
ugly[i] = Math.min(min, nc);

if (ugly[i] == na) a++;
if (ugly[i] == nb) b++;
if (ugly[i] == nc) c++;
}
return ugly[n - 1];
}
}


# 总结

原文作者：未见花闻
原文地址: https://blog.csdn.net/m0_59139260/article/details/121022143
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。