C语言求解第n个丑数

解题思路

先写一个丑数数列 1 2 3 4 5 6 8 9......

丑数定义：因子只含有2 3 5，那么一个丑数必然由前面的丑数乘积得来。这里维护三个指针，分别为i2，i3，i5用于记录当前数字乘以2 3 5的结果。i2 i3 i5都从0出发。第一个丑数1，那么第二个丑数必然是1*2 1*3 1*5中最小的，为2，此时丑数数列 1 2，而2是由i2 得来的，那么i2此时右移一位，i2指向第二个丑数2；接下来是第三位丑数 1 2，此时计算i2 i3 i5 得到的4 3 5，最小值为3，i3右移一位，指向2。以此类推...利用三个指针，计算第n个丑数

 * 
 * @param index int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int min3(int a,int b,int c){
    if(a<=b&&a<=c)
        return a;
    else if(b<=a&&b<=c)
        return b;
    else 
        return c;
}
int GetUglyNumber_Solution(int index ) {
    // write code here
    int ans[2000];
    // 分别记录X2 X3 X5
    int i2=0,i3=0,i5=0;
    if(index<=6)
        return index;
    ans[0]=1;
    //正向计算第n个丑数
    for(int n=1;n<index;n++){
        ans[n]=min3(ans[i2]*2,ans[i3]*3,ans[i5]*5);
        //如果是由前一个丑数乘以2得来的 那么i2指针右移
        if(ans[n]==ans[i2]*2)
            i2++;
       //如果是由前一个丑数乘以3得来的 那么i3指针右移
        if(ans[n]==ans[i3]*3)
            i3++;
        //如果是由前一个丑数乘以5得来的 那么i5指针右移
        if(ans[n]==ans[i5]*5)
            i5++;

    }
    return ans[index-1];
}