寻找丑数

[编程题]寻找丑数

热度指数：4893 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

输入描述:

整数N

输出描述:

第N个丑数

示例1

输入

输出

算法知识视频讲解

Java

飒飒的收到Z传说中

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.print(GetUglyNumber(sc.nextInt()));
        sc.close();
    }
    
    public static int GetUglyNumber(int index) {
        if(index<=6)
            return index;
        int[] arr=new int[index];
        arr[0]=1;
        int t2=0,t3=0,t5=0;
        for(int i=1;i<index;i++){
           arr[i]=(Math.min(arr[t2]*2,Math.min(arr[t5]*5,arr[t3]*3)));
            if(arr[i]==arr[t2]*2) t2++;
            if(arr[i]==arr[t3]*3) t3++;
            if(arr[i]==arr[t5]*5) t5++;
        }
        return arr[index-1];
    }
}

发表于 2019-09-15 23:53:02 回复(0)