丑数

题目描述

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

分析

这里的因子指的是质因子。

每个丑数等于某个比它小的丑数x2或x3或x5。
根据提示中的信息,我们知道丑数可以拆分成3个子序列:

  1. 1x2, 2x2, 3x2, 4x2, 5x2, 6x2, 8x2…
  2. 1x3, 2x3, 3x3, 4x3, 5x3, 6x2, 8x2…
  3. 1x5, 2x5, 3x5, 4x5, 5x5, 6x2, 8x2…

其中1,2,3,4,5,6,8(注意,没有7)是前几个丑数。7有因子7,所以不是丑数。

每次从三个子序列中取出当前最小的那个加入序列,直到第N个为止。

代码:

public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index <= 0) return 0;
int[] uglynum = new int[index];
uglynum[0] = 1;
int n = 0,index2 = 0,index3 = 0,index5 = 0,x2 = 0, x3 = 0, x5 = 0, min = 0;
while( n + 1 < index){
x2 = uglynum[index2] * 2;
x3 = uglynum[index3] * 3;
x5 = uglynum[index5] * 5;
min = Math.min(x2,Math.min(x3,x5));
if(min == x2) ++index2;
else if(min == x3) ++index3;
else ++index5;
if(min != uglynum[n])
uglynum[++n] = min;
}
return uglynum[index-1];
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :