⭐ 题目日期：

拼多多 - 2024/10/13

🌳 题目描述：

质因数分解，有些数可以只分解为2，3，5这三个质因数中的数，打印输出前n个这样的数。

示例：
输入：n = 10
输出：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

🧗难度系数：

⭐️ ⭐️ ⭐ ⭐

📝解题思路

根据题意，满足条件的所有丑数(方便起见，暂定为丑数)，均可表示为 uglyNumber = $2^{i}*3^{j}*5^{k}, i, j, k >= 0$

这样我们可以从 i = 0, j = 0, k = 0 开始第一个丑数：1，再在此基础上对所有丑数分别进行乘 2， 乘 3， 乘 5，从小到大排列，就能找到前 n 个丑数。

💻代码：

Java

 public int[] nUglyNumbers(int n) {
     int[] nums = new int[n];
     nums[0] = 1;
     int[] pointers = new int[3];
     for (int i = 1; i < n; i++) {
         nums[i] = Math.min(nums[pointers[0]] * 2, 
                   Math.min(nums[pointers[1]] * 3, nums[pointers[2]] * 5));
         if (nums[pointers[0]] * 2 == nums[i]) {
             pointers[0]++;
         }
         if (nums[pointers[1]] * 3 == nums[i]) {
             pointers[1]++;
         }
         if (nums[pointers[2]] * 5 == nums[i]) {
             pointers[2]++;
         }
     }
     return nums;
 }

🚵🏻复杂度分析：

时间复杂度：O(n), for 循环 n 次，每次常数级操作 空间复杂度：O(n), 用于存储计算好的丑数