Ugly number Java

2025年5月6日 | 阅读 5 分钟

丑陋数字是 Java 中另一种特殊的正数。如果一个数的素数因子只有 2、3 或 5，并且按照约定也包括 1，那么这个数就称为丑陋数字。

让我们看一些丑陋数字的例子。

27 不是丑陋数字，因为它的素数因子包含 7。
12 是丑陋数字，因为它的素数因子是 2 和 3。
28 也不是丑陋数字，因为它的素数因子也包含 7。
16 是丑陋数字，因为它的素数因子只包含 2。

在 Java 中，我们可以通过两种方法找到第 N 个丑陋数字。这些方法如下：

使用 for 循环的简单方法
使用动态规划

让我们逐一了解这两种方法，并实现它们各自的逻辑。

使用 for 循环的简单方法

在此方法中，我们使用循环遍历每个正数，直到丑陋数字计数不大于 n。当一个数字是丑陋数字时，我们增加计数器变量，并通过 2、3 和 5 的最大可整除幂来检查数字是否是丑陋数字。当数字变为 1 时，它就是一个丑陋数字。否则，它不是丑陋数字。

让我们实现代码以在 Java 中获取第 N 个丑陋数字。

UglyNumberExample1.java

//import required classes and packages
import java.io.*;
import java.util.*;

//create UglyNumberExample1 class to get Nth Ugly number
class UglyNumberExample1 {
 
    // create a method divideByGreatestDivisible() method for dividing the number by the given greatest divisible power
    static int divideByGreatestDivisible(int number, int gdp)
    {
        while (number % gdp == 0)
            number = number / gdp;
        return number;
    }
 
    // create checkUglyNumber() method that returns true when the number is an Ugly
    static boolean checkUglyNumber(int number)
    {
        number = divideByGreatestDivisible(number, 2);
        number = divideByGreatestDivisible(number, 3);
        number = divideByGreatestDivisible(number, 5);
 
        return (number == 1) ? true : false;
    }
 
    //create findNthUglyNumber() method for getting the nth Ugly number
    static int findNthUglyNumber(int NthNumber)
    {
        int number = 1;
 
        // initialize counter
        int counter = 1;
 
        // using  while loop to get Nth Ugly number
        while (NthNumber > counter) {
            number++;
            if (checkUglyNumber(number))
                counter++;	//increment counter value
        }
        return number;
    }
 
    //main() method start
    public static void main(String args[])
    {
		
        int NthNumber1, NthNumber2;
		
		//create scanner class object to get input from user
		Scanner sc = new Scanner(System.in);
		
		//show custom message
		System.out.println("Enter first Nth value");
		
		//store user entered value into variable NthNumber1
		NthNumber1 = sc.nextInt();
		
		//show custom message
		System.out.println("Enter second Nth value");
		
		//store user entered value into variable NthNumber2
		NthNumber2 = sc.nextInt();
		
        System.out.println("The " + NthNumber1 + "th Ugly number is: " + findNthUglyNumber(NthNumber1));
		System.out.println("The " + NthNumber2 + "th Ugly number is: " + findNthUglyNumber(NthNumber2));
    }
}

输出

同样，我们也可以实现代码来检查给定的数字是否是丑陋数字。

UglyNumberExample2.java

//import required classes and packages
import java.io.*;
import java.util.*;

//create UglyNumberExample2 class to check whether the given numbers are Ugly or not
class UglyNumberExample2 {
 
    // create a method divideByGreatestDivisible() method for dividing the number by the given greatest divisible power
    static int divideByGreatestDivisible(int number, int gdp)
    {
        while (number % gdp == 0)
            number = number / gdp;
        return number;
    }
 
    // create checkUglyNumber() method that returns true when the number is an Ugly
    static boolean checkUglyNumber(int number)
    {
        number = divideByGreatestDivisible(number, 2);
        number = divideByGreatestDivisible(number, 3);
        number = divideByGreatestDivisible(number, 5);
 
        return (number == 1) ? true : false;
    }
 
    //main() method start
    public static void main(String args[])
    {
		
        int number1, number2;
		
		//get input from user
		Scanner sc = new Scanner(System.in);
		System.out.println("Enter first number to check");
		number1 = sc.nextInt();

		System.out.println("Enter second number to check");		
		number2 = sc.nextInt();
		
		if (checkUglyNumber(number1)) 
            			System.out.println(number1 + " is an Ugly number."); 
        		else
            			System.out.println(number1 + " is not an Ugly number.");
		
		if (checkUglyNumber(number2)) 
            			System.out.println(number2 + " is an Ugly number."); 
        		else
            			System.out.println(number2 + " is not an Ugly number.");
    	}
}

输出

使用动态规划

还有另一种获取第 N 个丑陋数字的方法，它需要 O(n) 的额外空间。开头一些丑陋数字的序列是 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ……..

我们可以将上述序列分成三个子序列，使得每个组中的丑陋序列如下：

1×2, 2×2, 3×2, 4×2, 5×2, …
1×3, 2×3, 3×3, 4×3, 5×3, …
1×5, 2×5, 3×5, 4×5, 5×5, …

为了从序列中获取每个丑陋数字，我们使用类似归并排序的合并方法。

以下是使用动态规划获取第 N 个丑陋数字的步骤：

首先，我们为丑陋数字声明一个数组。
1 是第一个丑陋数字，所以我们在程序中将其初始化为第一个丑陋数字。
接下来，我们将 i2、i3、i5 初始化为数组索引变量，用于指向丑陋数组的第一个元素。
i2 = i3 = i5 =0;
初始化为下一个丑陋数字的选择，如下：
mulitple2 = ugly[i₂]*2;
mulitple3 = ugly[i₃]*3
mulitple5 = ugly[i₅]*5;
我们使用循环语句来填充给定范围内的所有丑陋数字。

for (i = 1; i <range; i++ ) 
{
nextUglyNumber  = Min(mulitple2, mulitple3, mulitple5); 
ugly[i] =  nextUglyNumber
if (nextUglyNumber  == mulitple2) 
{             
i2 = i2 + 1;        
mulitple2 = ugly[i2]*2;
} 
if (nextUglyNumber  == mulitple3) 
{             
i3 = i3 + 1;        	
mulitple3 = ugly[i3]*3;
}            
if (nextUglyNumber  == mulitple5)
{    
i5 = i5 + 1;        
mulitple5 = ugly[i5]*5;
} 
} 

最后，我们返回 nextUglyNumber。

让我们使用上述步骤，在 Java 中实现其实际代码。

UglyNumberExample3.java

//import required classes and packages
import java.io.*;
import java.util.*;

//create UglyNumberExample1 class to get the Nth ungly number
class UglyNumberExample3 {
 
    //create findNthUglyNumber() method for getting the nth Ugly number
    static int findNthUglyNumber(int number)
    {
         // declare an array for ugly numbers
        int uglyNumbers[] = new int[number];
		
		//we initialize i2, i3, i5  as array index variables for pointing to the 1st element of the ugly array: 
        int i2 = 0, i3 = 0, i5 = 0;
        
		int multiple2 = 2;
        int multiple3 = 3;
        int multiple5 = 5;
        
		int nextUglyNumber = 1;
 
        uglyNumbers[0] = 1;
 
        for (int i = 1; i < number; i++)
        {
            nextUglyNumber = Math.min(multiple2, Math.min(multiple3, multiple5));
 
            uglyNumbers[i] = nextUglyNumber;
            if (nextUglyNumber == multiple2)
            {
                i2 = i2 + 1;
                multiple2 = uglyNumbers[i2] * 2;
            }
            if (nextUglyNumber == multiple3)
            {
                i3 = i3 + 1;
                multiple3 = uglyNumbers[i3] * 3;
            }
            if (nextUglyNumber == multiple5)
            {
                i5 = i5 + 1;
                multiple5 = uglyNumbers[i5] * 5;
            }
        }
         
        // End of for loop (i=1; i<n; i++)
        return nextUglyNumber;
    }
 
    //main() method start
    public static void main(String args[])
    {
		
        int NthNumber1, NthNumber2;
		
		// use Scanner class for taking value of NthNumber1 and NthNumber2
		Scanner sc = new Scanner(System.in);
		
		//show custom message
		System.out.println("Enter first Nth value");
		
		//store user entered value into variable NthNumber1
		NthNumber1 = sc.nextInt();
		
		//show custom message
		System.out.println("Enter second Nth value");
		
		//store user entered value into variable NthNumber2
		NthNumber2 = sc.nextInt();
		
        System.out.println("The " + NthNumber1 + "th Ugly number is: " + findNthUglyNumber(NthNumber1));
		System.out.println("The " + NthNumber2 + "th Ugly number is: " + findNthUglyNumber(NthNumber2));
    }
}

输出

下一主题Friends-pairing-problem-in-java

Ugly number Java

使用 for 循环的简单方法

使用动态规划

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Ugly number Java

使用 for 循环的简单方法

使用动态规划

相关帖子

在线将 JSON 转换为 Java 对象

如何在 Java 中设置计时器

Java ContentPane

Java 中的 CountDownLatch

Binary to Gray Code Using Recursion in Java

Java 中的加法数

Java 中的 Boggle 搜索问题

Java 中的图像处理：将彩色图像转换为红色、绿色和蓝色图像

Java 并发中的 Lock 框架与线程同步

最流行的 Java 后端工具

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器