在Java中找到第N个丑数

什么是丑数

在数学中，丑数（Ugly Number）是指只包含质因子 2、3 和 5 的正整数。例如，前几个丑数为1、2、3、4、5、6、8、9、10、12等。其中，数字1被视为是第一个丑数。

问题描述

给定一个正整数n，要求找到第n个丑数。例如，当n=10时，结果为12。

解决方案

思路分析

我们可以考虑暴力枚举每个数字是否为丑数，然后通过计数器找到第n个丑数，但是这个方法的时间复杂度较高。

实际上，我们可以通过维护一个丑数集合来实现，每次向集合中添加最小丑数的2倍、3倍、5倍，直到集合的大小达到n，这时集合中的最后一个元素即为第n个丑数。

代码实现

public int nthUglyNumber(int n) {
    int[] nums = new int[n];
    nums[0] = 1; // 第一个丑数为1
    int index2 = 0, index3 = 0, index5 = 0;
    for (int i = 1; i < n; i++) {
        // 找到三个数的最小值
        int min = Math.min(nums[index2] * 2, Math.min(nums[index3] * 3, nums[index5] * 5));
        // 如果最小值与2相等，则将index2加1
        if (min == nums[index2] * 2) {
            index2++;
        }
        // 如果最小值与3相等，则将index3加1
        if (min == nums[index3] * 3) {
            index3++;
        }
        // 如果最小值与5相等，则将index5加1
        if (min == nums[index5] * 5) {
            index5++;
        }
        nums[i] = min; // 将最小值放入数组中
    }
    return nums[n - 1]; // 返回第n个丑数
}

代码说明

第1行：定义一个长度为n的数组nums，表示丑数集合。

第2行：将第一个丑数赋值为1。

第3-5行：分别定义三个指针，分别表示乘以2、3、5时需要比较大小的数在数组中的下标。

第6行：循环从1到n-1，依次计算每个丑数。

第8行：比较三个数的乘积的最小值。

第9-11行：如果最小值与2、3、5的乘积相等，则将对应的指针加1。

第12行：将最小值放入数组中。

第13行：返回第n个丑数。

测试结果

我们使用Junit进行单元测试，测试代码如下：

@Test
public void test() {
    Solution solution = new Solution();
    Assert.assertEquals(1, solution.nthUglyNumber(1));
    Assert.assertEquals(12, solution.nthUglyNumber(10));
    Assert.assertEquals(5832, solution.nthUglyNumber(150));
}

运行结果如下：

总结

本篇文章详细讲解了在Java中找到第N个丑数的解决方案，给出了相应的代码实现和测试结果。通过维护一个丑数集合来实现，每次向集合中添加最小丑数的2倍、3倍、5倍，直到集合的大小达到n，这时集合中的最后一个元素即为第n个丑数。这种方法的时间复杂度为O(n)。

在解决具体问题时，我们需要灵活应用各种数据结构和算法来提高代码的效率和性能。同时，我们还需要注重代码的可读性和可维护性，尽可能地使用命名规范、注释和代码风格规范等技巧，使代码更加易于理解和修改。