丑数

题目描述

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

思路

先说一个比较耗时的思路：判断一个数字是不是丑数，先让这个数除以2，知道不能整除，再除以3直到不能整除，再除以5，知道不能整除。最后这个数如果是1，那这个数就是丑数，否则不是丑数。 这个思路很好理解，一个一个的遍历判断就可以。但是计算量比较大，复杂度高。
第二个思路：首先想丑数是如何得来的。丑数肯定是由小的丑数乘上2，3，5得来的。那么从1开始，依次乘2，3，5，把结果放进去，肯定是丑数。 但是这样无法保证放进去的顺序是有序的，这里每次要把最小的丑数放进顺序列表里。通过3个指针，P2,P3,P5来解决这个问题。这三个指针开始均指向列表第一个元素，也就是1。三个指针分别代表三个因子数。同时自身也表示所在列表里的索引位置。每次在该索引位置乘对应的因子数，表示这个数目前的3种丑数变化。然后把这个三个数里最小的那个加入到列表。 下一步就是更新3个指针的位置，目的也是为了去除重复。当最小的值与该指针乘以系数相等，那么这个指针就前移一位。
宏观的理解流程就是每次找到最小的丑数，然后让这个丑数分别乘以2，3，5三个因子，把里面最小的存下，剩下2个值（不考虑重复）放入候选池，等下一个丑数的时候再比较选择。

代码

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
         # write code here
        if index == 0:
            return 0
        result = []
        result.append(1)
        p2 = 0
        p3 = 0
        p5 = 0
        for i in range(index-1):
            v1 = result[p2] * 2
            v2 = result[p3]*3
            v3 = result[p5] * 5
            min_val = min(v1, v2, v3)
            result.append(min_val)
            if min_val == v1:
                p2 = p2 + 1
            if min_val == v2:
                p3 = p3 + 1
            if min_val == v3:
                p5 = p5 + 1
        ans = result[-1]
        return ans