1 /************************************************************************* 2     > File Name: 32_UglyNumber.c 3     > Author: Juntaran 4     > Mail: JuntaranMail@gmail.com 5     > Created Time: 2016年09月02日 星期五 12时29分59秒 6  ************************************************************************/ 7  8 #include <stdio.h> 9 #include <malloc.h>10 11 int isUgly(int number)12 {13     while (number % 2 == 0)14         number /= 2;15     while (number % 3 == 0)16         number /= 3;17     while (number % 5 == 0)18         number /= 5;19     20     return (number==1) ? 0 : -1;21 }22 23 // 低效方法24 int getUglyNumber1(int n)25 {26     if (n <= 0)27         return -1;28     29     int number = 0;30     while (n != 0)31     {32         ++ number;33         if (isUgly(number) == 0)34             n --; 35     }36     printf("%d\n", number);37     return number;38 }39 40 int MinOfThree(int a, int b, int c)41 {42     int minNum = a>b ? b : a;43     minNum = minNum>c ? c : minNum;44     return minNum;45 }46 47 // 高效方法 空间换时间48 int getUglyNumber2(int index)49 {50     if (index <= 1)51         return index;52     53     int* ugly = (int*)malloc(sizeof(int) * index);54     int i2 = 0;55     int i3 = 0;56     int i5 = 0;57     ugly[0] = 1;58     59     for (int i = 1; i < index; ++i)60     {61         int temp2 = ugly[i2] * 2;62         int temp3 = ugly[i3] * 3;63         int temp5 = ugly[i5] * 5;64         65         int minNum = MinOfThree(temp2, temp3, temp5);66         ugly[i] = minNum;67         68         if (minNum == temp2)69             i2 ++;70         if (minNum == temp3)71             i3 ++;72         if (minNum == temp5)73             i5 ++;74     }75     printf("%d\n", ugly[index - 1]);76     return ugly[index - 1];77 }78 79 int main()80 {81     getUglyNumber1(1500);82     getUglyNumber2(1500);83 }