剑指33-丑数

Posted on | In |

题目描述

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

定义了一个丑数递增序列L,和列表L上的三个下标ix2、ix3、ix5为：

  • ix2是满足2*L[ix2]>L[-1]的最小,
  • ix3是满足3*L[ix3]>L[-1]的最小,
  • ix5是满足5*L[ix5]>L[-1]的最小。

其中L[-1]是列表L的最后一个元素。

由于丑数是只包含质因子2、3和5的数，那么下一个丑数必然出自L[ix2]*2,L[ix3]*3,L[ix5]*5这三个数。

可以证明：如果L[ix2]*2被选中，则更新公式必然是ix2 += 1。如下证明ix2+1是满足2*L[ix2+1]>L[ix2]*2的最小：

  • 由于L[ix2+1]>L[ix2],则L[ix2+1]*2>L[ix2]*2=L[-1]，这里L[-1]是刚添加进L的L[ix2]*2。即ix2+1必然满足。
  • 不存在ix<ix2+1，使得L[ix]*2>L[-1]。因为此时必有ix<=ix2,必有L[ix]*2<=L[ix2]*2=L[-1]。即ix2+1必然最小。

同理可得ix3和ix5的更新公式。如果有多与一个序号被选中，即L[ix2]*2,L[ix3]*3,L[ix5]*5里有大于1个数相等且为下一个丑数，此时对应的序号分别更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def GetUglyNumber_Solution(self, index):
        if (index <= 0):
            return 0
        L = [1]
        ix2, ix3, ix5 = 0, 0, 0
        for i in range(index-1):
            newUgly = min(L[ix2]*2, L[ix3]*3, L[ix5]*5)
            L.append(newUgly)
            if (newUgly % 2 == 0):
                ix2 += 1
            if (newUgly % 3 == 0):
                ix3 += 1
            if (newUgly % 5 == 0):
                ix5 += 1
        return L[-1]