题目描述：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
问题分析：根据丑数定义，可以从1开始依次把每个已经存在于丑数数组的数分别与2，3，5进行相乘，并取乘积中最小的数将其放入丑数数组。
我们可以对2，3，5分别建立一个乘积队列，将每次与从丑数数组中取出的数的乘积添加到队尾，同时将队首的数中最小的数出队列并放到丑数数组中，如果存在队首有相同的数，则均出队列。方便起见，可以用指针代替乘积队列，指针指向当前队首元素，也表示取丑数数组中第几个数作为乘数。具体流程如下图：
动态示意图
代码截图：
网友评论