剑指offer 丑数

Posted on |

丑数

题目

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

方法

只包含因子2，3，5的数称为丑数。第一个丑数是1。

将已有的丑数乘上因子2，3，5，可以得到更多的丑数，但是我们必须做好排序，以及希望不必把已有的丑数都乘以因子2，3，5。因为丑数都是按顺序存放在数组中。对于乘以因子2而言，肯定存在某一个丑数$T_2$，排在他之前的丑数乘以2都小于已有的最大的丑数，在他之后的丑数乘以2都大于已有的最大的丑数。我们只需要记下这个丑数$T_2$的位置，同时每次生成新的丑数的时候，都去更新这个$T_2$的位置。因子3和5也同样操作，得到$T_3，T_5$
特殊输入测试：边界值1；无效输入0
性能测试：输入较大的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index<=0:     # 当输入index==0，应该返回0
            return 0
        uglyNumbers=[1]*index
        nextIndex=1

        index2,index3,index5=0,0,0

        while nextIndex<index:
            # 生成新的丑数，因为排序关系，所以这是当前丑数数组中最大的丑数
            uglyNumbers[nextIndex]=min(uglyNumbers[index2]*2,uglyNumbers[index3]*3,uglyNumbers[index5]*5)

            # 更新丑数后，更新$T_2,T_2,T_3$的索引
            while uglyNumbers[index2]*2<=uglyNumbers[nextIndex]:
                index2+=1
            while uglyNumbers[index3]*3<=uglyNumbers[nextIndex]:
                index3+=1
            while uglyNumbers[index5]*5<=uglyNumbers[nextIndex]:
                index5+=1
            # 更新下个丑数的索引
            nextIndex+=1
        return uglyNumbers[-1]