把只包含质因子2、3和5的数称作丑数(Ugly Number)

in 编程
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9

//超时

public class Solution {

public int GetUglyNumber_Solution(int index) {
    if(index==1)
        return 1;
    int sum=1;
    int n=1;
    int res=1;
    
    while(true){
        n++;
        if(f(n))
            sum++;
        if(sum==index) 
            return n;
    }
    
}

public boolean f(int n){
    
    int a[]={2,3,5};
    
    int len=a.length;
    
    int i=0;
    
    int sum=1;
    
    int temp = n;
    while(i<len){
        if(sum==n)
            return true;
        else if(sum>n)
            return false;
        else if(temp%a[i]==0){
            sum=sum*a[i];
            temp=temp/a[i];
        }
        else
            i++;
    }
    return false;
}

}

//可行的方案

import java.util.*;

public class Solution {

public int GetUglyNumber_Solution(int index) {

    if(index<1)
        return 0;
  int a[]=new int[index];
    a[0]=1;
    
    int i1=0,i2=0,i3=0;
    int temp1;
    for(int i=1;i<a.length;i++){
        temp1=Math.min(a[i1]*2,a[i2]*3);
        a[i]=Math.min(temp1,a[i3]*5);
        
        if(a[i]==a[i1]*2) i1++;
        if(a[i]==a[i2]*3) i2++;
        if(a[i]==a[i3]*5) i3++;
    }
                      
    return a[index-1];
}

}

关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9
扫一扫关注公众号添加购物返利助手,领红包
Comments are closed.

推荐使用阿里云服务器

超多优惠券

服务器最低一折,一年不到100!

朕已阅去看看