丑数

因子只含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 ;
}
05-04 01:51