【剑指offer】丑数的查找 python

【剑指offer】丑数的查找 python

自己看了很久，没有想出来，借鉴了下其他人分享的思路，总算是理解了。

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

思路
这里主要有两条思路：
1、按照顺序依次判断整数是否为丑数，条件（因子只有2，3，5），这种方法费时比较长，不是首选；
2、依照丑数的定义，按顺序求出下一个丑数。这里主要展示这种方法的代码。

这里的思路主要是要将丑数看作是现有2，3，5倍，既然都是2，3，5的倍数，那么分别为2，3，5建立倍数索引，如果下一个丑数刚好是某个丑数的2倍，那对应倍数索引＋1，再次寻找最小值时，其备选项将变为为新丑数的2倍，

这里要注意2 * 3，3 * 2这类存在相同的值，因此需要逐一验证，不可直接跳出循环。

import timedef GetUglyNumber_Solution(index):"""除1外，丑数主要来源于现有丑数的2， 3， 5倍，"""if index <= 0:return 0if index == 1:return 1ugly_lists = [1]# 为2，3，5创建倍数索引，i_2, i_3, i_5 = 0, 0, 0for i in range(1, index):# 下一个丑数来源于未加入的2， 3，5倍数值的最小值new_ugly = min([ugly_lists[i_2] * 2, ugly_lists[i_3] * 3, ugly_lists[i_5] * 5])ugly_lists.append(new_ugly)# 找到最小值来源于2， 3， 5中的哪个倍数值，对应索引值＋1，# 这里要注意2*3，3*2这类存在相同的值，因此需要逐一验证，不可直接跳出循环。if ugly_lists[i] == ugly_lists[i_2] * 2:i_2 += 1if ugly_lists[i] == ugly_lists[i_3] * 3:i_3 += 1if ugly_lists[i] == ugly_lists[i_5] * 5:i_5 += 1return ugly_lists[-1]if __name__ == '__main__':for i in range(10):print(GetUglyNumber_Solution(i))t = time.clock()print(GetUglyNumber_Solution(1000))print("运行时间：", time.clock())

运行结果如下：

参考：
丑数–python实现：；
[剑指Offer]丑数[Python] ：； （ps 这个讲的很详细呢)

【剑指offer】丑数的查找 python

自己看了很久，没有想出来，借鉴了下其他人分享的思路，总算是理解了。

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

思路
这里主要有两条思路：
1、按照顺序依次判断整数是否为丑数，条件（因子只有2，3，5），这种方法费时比较长，不是首选；
2、依照丑数的定义，按顺序求出下一个丑数。这里主要展示这种方法的代码。

这里的思路主要是要将丑数看作是现有2，3，5倍，既然都是2，3，5的倍数，那么分别为2，3，5建立倍数索引，如果下一个丑数刚好是某个丑数的2倍，那对应倍数索引＋1，再次寻找最小值时，其备选项将变为为新丑数的2倍，

这里要注意2 * 3，3 * 2这类存在相同的值，因此需要逐一验证，不可直接跳出循环。

import timedef GetUglyNumber_Solution(index):"""除1外，丑数主要来源于现有丑数的2， 3， 5倍，"""if index <= 0:return 0if index == 1:return 1ugly_lists = [1]# 为2，3，5创建倍数索引，i_2, i_3, i_5 = 0, 0, 0for i in range(1, index):# 下一个丑数来源于未加入的2， 3，5倍数值的最小值new_ugly = min([ugly_lists[i_2] * 2, ugly_lists[i_3] * 3, ugly_lists[i_5] * 5])ugly_lists.append(new_ugly)# 找到最小值来源于2， 3， 5中的哪个倍数值，对应索引值＋1，# 这里要注意2*3，3*2这类存在相同的值，因此需要逐一验证，不可直接跳出循环。if ugly_lists[i] == ugly_lists[i_2] * 2:i_2 += 1if ugly_lists[i] == ugly_lists[i_3] * 3:i_3 += 1if ugly_lists[i] == ugly_lists[i_5] * 5:i_5 += 1return ugly_lists[-1]if __name__ == '__main__':for i in range(10):print(GetUglyNumber_Solution(i))t = time.clock()print(GetUglyNumber_Solution(1000))print("运行时间：", time.clock())

运行结果如下：

参考：
丑数–python实现：；
[剑指Offer]丑数[Python] ：； （ps 这个讲的很详细呢)