丑数

问题描述

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

思路分析

由丑数的定义知道丑数只有以上三个因子,所以在排序的丑数列表中,后面的某个丑数一定是前面某个丑数乘以2或3或5的结果,所以我们以这三个因子的到的丑数进行排序,把最小的丑数更新到丑数列表中,如果刚好是丑数中的最小值,则把该数对应的下标加1,然后继续寻找下一个丑数

码上有戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int GetUglyNumber_Solution(int index) {
if(index<=0)return 0;
int[] ugly=new int[index];
ugly[0]=1;
int count=1;
int num2=0;
int num3=0;
int num5=0;
while(count<index){
int min=IsUglyNumber(ugly[num2]*2,ugly[num3]*3,ugly[num5]*5);
ugly[count]=min;
count++;
if(min==ugly[num2]*2)
num2++;
if(min==ugly[num3]*3)
num3++;
if(min==ugly[num5]*5)
num5++;
}
return ugly[index-1];
}
private int IsUglyNumber(int num2,int num3,int num5){
int min=num2<num3?num2:num3;
return min<num5?min:num5;
}

热评文章