题解 | #丑数#

丑数

http://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b

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];
}
全部评论

相关推荐

你今天学到了啥:9硕都比不上9本
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
09-10 15:43
不想上班蚊不叮在走神:华子是这样的。我投递了,还有其他华子内部人加我,不知道从哪搞的微信号,还要给我打电话劝我改投递方向。直接不鸟就行了
点赞 评论 收藏
分享
白也ya:今天也是狠狠的被boss拷打了😋,终于知道双非想约到面试有多难了
点赞 评论 收藏
分享
1 1 评论
分享
牛客网
牛客企业服务