这个题第一次看到的时候，首先想到的是一个一个列出数字，依次判断是不是丑数并且累计次数。
#include <stdio.h>
int Isuglynumber(int i)
{
if (i == 2 || i == 3 || i == 5)return 1;else{
int j = i;while (1){
if (j % 2 == 0)j = j / 2;else if (j % 3 == 0)j = j / 3;else if (j % 5 == 0)j = j / 5;elsereturn 0;if (j == 2 || j == 3 || j == 5)return 1;}}
}
int GetUglyNumber_Solution(int index) {
// write codhereif (index == 1)return 1;int count = 1;int i = 1;int j = 0;while (count != index){
i++;j = Isuglynumber(i);if (j == 0)continue;elsecount++;}return i;
}
int main()
{
int k = 0;scanf("%d", &k);printf("%d", GetUglyNumber_Solution(k));
}
这样可以达到效果，但是实测发现，当输入较大的数字时，需要很长的时间来计算，效率很低下。（输入1500，要过大概十秒左右才出结果）
（你看这个算法啊，才多少数就醉了，真的太逊了）
因此，不得不转换一下我们的思路。
经过思考不难发现，其实靠后的丑数，是可以凭借前面的丑数依次乘以2、3、5得到的。因此可以创建一个数组用于保存之前的丑数，以空间换时间，来节省遍历所耗费的大量时间。
思路：首先用三个指针（乘2、乘3、乘5的指针）指向数组第一个出现的丑数（也就是1），然后这三个指针指向的元素依次乘以2、3、5，再用乘积与数组中最后一个丑数进行对比。如果这个乘积是大于数组中最后一个数，那么我们先不要将指针指向下一位，将这个乘积保存下来，与其他乘积相比较，留存最小的数进行增加，因为我们要按照从小到大的顺序来往数组中增添丑数；如果这个乘积小于或等于了最大的丑数，那么说明当前指针指向的元素已经“过时”了，所以要把他向后移动一个单位，并且记录下来他新指向的元素和他自身倍数的乘积。
由于作者表达能力有限，上面这段阐述可能显得有些晦涩难懂。用图解来解释一下。
这是开始的数组
1
仅有一个数字。
此时三个指针（乘2、乘3、乘5的指针）都指向这个元素。
此时把三个指针指向的元素分别乘上自身的倍数，并且比较出最小值。
三个乘积分别为2、3、5。他们的最小值是2，把他填到数组末尾。
现在的数组：
1 2
三个指针指向的元素都是1，而1*2等于2，这个2并不大于当前数组最右端的丑数，因此，我们认为这个“乘2”的指针已经“过时”了，所以让他指向下一个元素2，并且把它的乘积也更新为新指向的元素乘以2.而剩下的两个指针自身分别的乘积为3、5，他们都大于2，并没有“过时”。
此时三个乘积变为了4、3、5，找到最小的3填到数组末端。
现在的数组：1 2 3
三个指针指向的元素和自身倍数的乘积：4，3，5
此时这个3的指针已经过时了，此时乘3的指针指向1，我们把他向后移动一个单位，他指向了2.此时三个数的乘积变为了4、6、5，最小的数变为了4.
…
下面便是如何实现。
```c
//首先实现一个求最小值的函数，在后面会用得到
int GetMin(int a,int b,int c)
{
if(a <= b && a <= c)return a;else if(b <= c && b <= a)return b;elsereturn c;
}
int GetUglyNumber_Solution(int index )
{
int arr[index];if(index < 7)//小于7的丑数直接返回自身就可以return index;else//这是大于7时的方案{
arr[0] = 1;//首先把数组第一个元素初始化为1，作为万物之伊始int temp2 = 0,temp3 = 0,temp5 = 0,j = 0,p2,p3,p5;/*temp2、temp3、temp5代表了三个乘积的指针，p2、p3和p5则记录了当前其对应的指针指向的值与自身倍数的乘积。j用来判断是否到达了要求丑数的范围。*/while(j < index){
if(arr[temp2]*2 > arr[j])p2 = arr[temp2]*2;/*如果当前的乘积大于最右端丑数，指针无需移动，只需记录下这个乘积*/elsep2 = arr[++temp2]*2;//这个与上一语句的差别仅在于是否移动指针//下面均同理if(arr[temp3]*3 > arr[j])p3 = arr[temp3]*3;elsep3 = arr[++temp3]*3;if(arr[temp5]*5 > arr[j])p5 = arr[temp5] * 5;elsep5 = arr[++temp5] * 5;arr[++j] = GetMin(p2,p3,p5);/*最后比较一下三个乘积的最小值，别忘了要++j把他加在当前数组末尾的下一位*/}}return arr[index-1];
}
int main()
{
int k = 0;scanf("%d", &k);printf("%d", GetUglyNumber_Solution(k));
}