本文主要是介绍[Lintcode]4. Ugly Number II/[Leetcode]264. Ugly Number II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
4. Ugly Number II / 264. Ugly Number II
- 本题难度: Medium
- Topic: Data Structure
Description
Ugly number is a number that only have factors 2, 3 and 5.
Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12…
Example
Example 1:
Input: 9
Output: 10
Example 2:
Input: 1
Output: 1
Challenge
O(n log n) or O(n) time.
Notice
Note that 1 is typically treated as an ugly number.
我的代码 超时。因为每个数都要判断一次
def nthUglyNumber(self, n: 'int') -> 'int':cur = 1while(n-1):cur += 1if self.isUgly(cur):n -= 1 return curdef isUgly(self, n):ugly = [2,3,5]for i in ugly:while(n % i == 0):n //= ireturn n == 1
别人的代码
class Solution:def nthUglyNumber(self, n: 'int') -> 'int':res = [1]i2 = i3 = i5 = 0while(n>1):u2, u3, u5 = 2*res[i2], 3*res[i3], 5*res[i5]uCurr = min(u2,u3,u5)if uCurr == u2:i2 += 1if uCurr == u3:i3 += 1if uCurr == u5:i5 += 1res.append(uCurr)n -= 1return res[-1]
思路
非常巧妙的思路。
所有ugly number都是由2,3,5组成的,所以他们肯定都是由2,3,5乘以之前的数得到,i2,i3,i5记录的分别是当前还未被乘2,3,5过的数字,接下来的ugly number肯定在其中,因为比它们更小的都已经在res中了
- 时间复杂度 O(n)
这篇关于[Lintcode]4. Ugly Number II/[Leetcode]264. Ugly Number II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!