剣指Offer(三十三):丑数

剣指Offer(三十三):丑数
微信の公衆番号を検索します:'AI-ming 3526'あるいは'コンピュータの視覚のこの小さい事'はもっと多くのアルゴリズムを獲得して、機械は乾物csdnを勉強します:https://blog.csdn.net/baidu_31657889/github:https://github.com/aimi-cn/AILearners
一、リード
このシリーズは私が牛客のネット上で《剣指Offer》のブラシのノートを磨いて、自分のアルゴリズムの能力を高めることを目的としています.完全な剣指Offerアルゴリズムの問題の解析を表示するにはCSDNとgithubリンクをクリックしてください:剣指Offer完全な練習問題の解析CSDNアドレスgithubアドレス
二、テーマ
素因数2,3,5のみを含む数をブス数(Ugly Number)と呼ぶ.例えば、6、8はすべて醜数であるが、14は質量因子7を含むためではない.習慣的に私たちは1を最初の醜数と見なしています.小さいから大きい順のN番目の丑数を求めます.
1、考え方
1つの数mとは別の数nの因子であり、nがmで除去される、すなわちn%m=0を指す.丑数の定義によると、丑数は2、3、5でしか除去できない.ブス数の定義によれば、ブス数は別のブス数に2、3または5を乗じた結果(1を除く)であるべきである.したがって、配列を作成することができます.中の数字は順番に並べられた丑数で、各丑数は前の丑数に2、3、または5を乗じて得られます.
この考え方の肝心な問題は,配列内の醜数が順序付けされていることをどのように保証するかである.2を乗じると、ある丑数T 2が必ず存在し、その前の各丑数に2を乗じた結果は、既存の最大の丑数よりも小さくなり、その後の各丑数に2を乗じた結果は大きすぎる.私たちはこの丑数の位置をメモするだけで、同時に新しい丑数を生成するたびに、このT 2を更新します.3と5を乗じた場合にも同様のT 3とT 5が存在する.
2、プログラミング実現
python
コード実装方式:

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index < 7:
            return index
        res = [1, 2, 3, 4, 5, 6]
        # res[t2]=4 4*2=8   res  4*1    res[t3]=3 3*3=9   res  3*2   res[t5]=2 5*2=10   res  5*1   
        t2, t3, t5 = 3, 2, 1
        for i in range(6, index):
            res.append(min(res[t2] * 2, res[t3] * 3, res[t5] * 5))
            while res[t2] * 2 <= res[i]:
                t2 += 1
            while res[t3] * 3 <= res[i]:
                t3 += 1
            while res[t5] * 5 <= res[i]:
                t5 += 1
        return res[index - 1]

AIMI-CN AI学習交流群【1015286623】より多くのAI資料を取得
技術を分かち合い、生活を楽しむ:私たちの公衆番号のコンピュータの視覚という小さなことは毎週「AI」シリーズの情報類の文章を送って、あなたの関心を歓迎します!