2019-02-04
2019-02-04 本文已影响0人
ruicore
LeetCode 264. Ugly Number II.jpg
LeetCode 264. Ugly Number II
Description
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example:
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note:
1 is typically treated as an ugly number.
n does not exceed 1690.
描述
编写一个程序，找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
思路
- 整型范围内(2^32)内一共有1690个丑数.
- 根据丑数的定义，num = 2^i * 3^j * 5^k.假设当前的丑数是n，下一个丑数num1一定是n*2，下二个丑数num2一定是n*3，n*5,num1*2 三个数中较小的一个.
- 丑数乘以2，或3，或5都是丑数，并且当前的丑数一定会被乘以2，乘以3，乘以5来产生新的丑数，只不过相乘所得到的结果并不是连续出现。比如当前丑数是n，下一个丑数num1是n*2,再下一个丑数是num1*2，接下来才是n*3。于是我们用i，j，k分别表示当前丑数乘以2，3，5，并取所乘最小的丑数作为下一个丑数，然后刚才被选中的丑数向后移动一个.
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-02-04 13:35:56
# @Last Modified by: 何睿
# @Last Modified time: 2019-02-04 14:25:45
class Solution:
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
uglynum = [1]
# i:2的次数，j:3的次数，k：5的次数，count：丑数的个数
# i表示当前位置的丑数乘以2
# j表示当前位置的丑数乘以3
# k表示当前位置的丑数乘以5
i, j, k, count = 0, 0, 0, 1
while count < n:
# 我们以对应的上一个数为基底，分别对应乘上2，3，5，
# 新的丑数一定是i，j，k位置的丑数对应乘以2，3，5中的最小数
uglyi, uglyj, uglyk = uglynum[i] * 2, uglynum[j] * 3, uglynum[k] * 5
# 然后我们选择最小的数
uglynext = min(uglyi, uglyj, uglyk)
# 如果uglynext == uglyi，说明当前位置的丑数乘以2得到新的丑数
# i自增一次表示用下一个数乘以2产生新的丑数
if uglynext == uglyi: i += 1
# 如果uglynext == uglyj，说明当前位置的丑数乘以3得到新的丑数
# j自增一次表示用下一个数乘以3产生新的丑数
if uglynext == uglyj: j += 1
# 如果uglynext == uglyk，说明当前位置的丑数乘以5得到新的丑数
# k自增一次表示用下一个数乘以5产生新的丑数
if uglynext == uglyk: k += 1
uglynum.append(uglynext)
count += 1
# 返回最后一个数字
return uglynum[-1]
