大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

剑指offer:丑数

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

定制设计可以根据自己的需求进行定制,成都网站设计、做网站构思过程中功能建设理应排到主要部位公司成都网站设计、做网站的运用实际效果公司网站制作网站建立与制做的实际意义

# -*- coding: utf-8 -*-
# @Time         : 2019-07-11 23:24
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : getUglyNumber.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

class Solution:
    """
    题目中丑数的定义是只包含因子2,3,5的数,特别地,1是第一个丑数。

    解法1:
    从1开始,逐个判断每个数字是不是丑数,如果是,则计数器加一,直到找到所要求的第n个丑数为止。
    但是这样做的话会对很多非丑数进行计算,时间复杂度太高。

    解法2:
    定义一个数组,用于按顺序保存已经找到的丑数,再定义三个指针p2, p3, p5,其中p2指向数组中第一个
    乘以2之后会比当前数组中末尾元素要大的数字;p3和p5同理。这样,当p2 * 2之后就会比当前最后一个
    丑数要大,而当p3 * 3 之后也会比最后一个丑数要大, p5同理。这样,当前最后一个丑数之后的第一个
    丑数就出现在p2 * 2, p3 * 3, p5 * 5之间,我们只需要比较这三个数的大小即可找到下一个丑数。
    注意每找到一个这样的丑数之后我们就要更新p2, p3, p5,直到我们找到足够多的丑数。
    这种方法是以空间换时间,我们维护了一个长度为n的数组,并最终返回这个数组的末尾元素。
    """
    def GetUglyNumber_Solution(self, index):
        if index <= 0:
            return 0

        uglyNumbers = [1] * index  # 用于保存已找到丑数的数组
        p2 = p3 = p5 = 0
        idx = 1

        while idx < index:
            # 每次都这三个数中找一个最小的作为下一个丑数
            nextUglyNumber = min(uglyNumbers[p2] * 2,
                                 uglyNumbers[p3] * 3,
                                 uglyNumbers[p5] * 5)
            uglyNumbers[idx] = nextUglyNumber

            # 然后更新这三个指针
            while uglyNumbers[p2] * 2 <= nextUglyNumber:
                p2 += 1
            while uglyNumbers[p3] * 3 <= nextUglyNumber:
                p3 += 1
            while uglyNumbers[p5] * 5 <= nextUglyNumber:
                p5 += 1

            idx += 1

        return uglyNumbers[index - 1]

def main():
    solution = Solution()
    index = 1
    print(solution.GetUglyNumber_Solution(index))

if __name__ == '__main__':
    main()

网页题目:剑指offer:丑数
本文链接:http://dzwzjz.com/article/ihscgs.html
在线咨询
服务热线
服务热线:028-86922220
TOP