【归并排序】264. 丑数 II

264. 丑数 II

解题思路

初始化一个数组 ugly 用于存储丑数，初始值为 [1]，表示第一个丑数是 1。

初始化三个指针 index2、index3 和 index5 分别为 0。

从 1 开始循环，计算每个位置的丑数。在每一轮循环中，计算乘以 2、3 和 5 得到的候选丑数，选择其中最小的作为当前丑数，并更新对应因子的指针。

循环直到计算出第 n 个丑数。

返回数组中的第 n 个丑数。

class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;// 默认第一个丑数是1

        int index2 = 0;
        int index3 = 0;
        int index5 = 0;// 三个指针

        // 核心思想：每一个丑数都是有基础的丑数组成的

        for(int i = 1; i < n; i++){
            // 三个数选择其中一个最小的 类似归并排序

            int factor2 = 2 * ugly[index2];
            int factor3 = 3 * ugly[index3];
            int factor5 = 5 * ugly[index5];

            int min = Math.min(Math.min(factor2,factor3),factor5);

            ugly[i] = min;// 更新最小的丑数

            if(factor2 == min){
                index2++;
            }

            if(factor3 == min){
                index3++;
            }

            if(factor5 == min){
                index5++;
            }
        }

        return ugly[n - 1];
    }
}