丑数

1.本题知识点

   时间空间效率的平衡

2. 题目描述

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

3. 思路

   总的来说，因为丑数的因子只有2,3,5，所以一个丑数肯定是由另一个丑数乘以2或乘以3或乘以5得到。比如，4,6,10是丑数，它们是由2乘以2,3,5得到的。

   所以，我们可以从最小的丑数开始，依次乘以2,3,5得到第2小的丑数，再乘以2,3,5得到第3小的丑数，一直找下去即可。

   我们需要3个指针和1个数组来实现，具体思路如下：

   我们要把3个指针当成3个队列，唯一的数组就是丑数数组。

   Java 版:

import java.util.ArrayList; public class Solution { public int GetUglyNumber_Solution(int index) { if(index < 0) return -1; //因为0~6都是丑数，直接返回index if(index < 7) return index; //定义乘以2,3,5的指针 int p2 = 0,p3 = 0,p5 = 0,minNum = 1; //丑数数组初始化 ArrayList<Integer> arr = new ArrayList<>(); arr.add(minNum); while(arr.size() < index ){ //取3个队列头最小的数 minNum = Math.min(arr.get(p2)*2,Math.min(arr.get(p3)*3,arr.get(p5)*5)); //把指针当成队列看好理解 if(arr.get(p2)*2 == minNum) p2++; if(arr.get(p3)*3 == minNum) p3++; if(arr.get(p5)*5 == minNum) p5++; //将下一个丑数加入到数组中 arr.add(minNum); } return arr.get(index-1);// 或者 return minNum 都可以 } }

4. 时间复杂度分析

   如果直接用循环的方式每一个数字都判断，时间复杂度为O(n)，空间复杂度O(1)。但是，上述思路中，我们用一个数组存储丑数并充分利用了丑数的性质，非丑数时不再计算，换取了部分时间，所以效率会提升。