剑指offer—

丑数

因子只含2,3,5的数称为丑数。

怎么求第K大的丑数呢。K可以为10^7

最简单的做法是，对每个数判断是否为丑数。复杂度为O( n * log(n) )，理论上是不行的。

uglys[i] 来保存所有丑数，uglys[0] = 1

因为要按从小到大产生一个新的丑数。这个丑数必然为之前某个丑数乘2或者乘3或者乘5。

我们维护三个index。

index_2：表示使得uglys[index_2] * 2 大于当前最大丑数时的最小下标。

index_3：表示使得uglys[index_3] * 3 大于当前最大丑数时的最小下标。

index_5：表示使得uglys[index_5] * 5 大于当前最大丑数时的最小下标。

而新产生的丑数必然为uglys[index_2]、 uglys[index_3]、uglys[index_5]中最小的一个。

而维护这三个下标，只要不停+1，直到大于当前最大丑数即可。

#include <stdio.h>

#include <iostream>

using namespace std;

class Solution {

public:

    int my_min(int x1, int x2) {

        if (x1 < x2) return x1;

        return x2;

    }

    int GetUglyNumber_Solution(int index) {

        int* uglys = new int[];

        int ugly_cnt = ;

        uglys[ugly_cnt++] = ;

        int index_2 = ;

        int index_3 = ;

        int index_5 = ;

        while (ugly_cnt < index) {

            while (uglys[index_2] *  <= *(uglys + ugly_cnt - )) {

                index_2++;

            }

            while (uglys[index_3] *  <= uglys[ugly_cnt - ]) {

                index_3++;

            }

            while (uglys[index_5] *  <= uglys[ugly_cnt - ]) {

                index_5++;

            }

            int min_ugly = my_min(uglys[index_2] * , my_min(uglys[index_3] *, uglys[index_5] * ));

            uglys[ugly_cnt++] = min_ugly;

        }

        printf("%d\n", uglys[ugly_cnt - ]);

        delete[] uglys;

        return ;

    }

};

int main() {

    Solution so;

    int n;

    cin >> n;

    so.GetUglyNumber_Solution(n);

    return ;

}

巴特西

剑指offer——49

最新文章

热门文章