David Aaronson
0%

第N个丑数

发表于 更新于 分类于
本文字数： 997 阅读时长 ≈ 1 分钟

题目描述

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

思路

  暴力求解思路。首先我们要搞清楚怎么求丑数。ugly[]表示丑数数组。

  1. ugly[0]=1;
  2. ugly[1]=1*2;
  3. ugly[3]=1*3;
  4. ugly[4]=122;
  5. ugly[5]=1*5;
  6. ugly[6]=123;
  7. …
      是不是可以找出规律来，我们需要记录 丑数中因子 2,3,5 出现的次数。具体用语言不好描述，可以看出规律。

代码

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
27
28
29
30
31
32
33
34
35
/**
 * 把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。
 * 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 * 
 * @author XIAO
 *
 */

public class GetUglyNumber {
	public int GetUglyNumber_Solution(int index) {
		if (index <= 0) {
			return 0;
		}
		int[] result = new int[index];
		result[0] = 1;
		int i2 = 0, i3 = 0, i5 = 0;// i2,i3,i5分别记录丑数的因子中2,3,5的个数
		for (int i = 1; i < index; i++) {
			result[i] = min(result[i2] * 2, min(result[i3] * 3, result[i5] * 5));
			if (result[i] == result[i2] * 2) {
				i2++;
			}
			if (result[i] == result[i3] * 3) {
				i3++;
			}
			if (result[i] == result[i5] * 5) {
				i5++;
			}
		}
		return result[index - 1];
	}

	private int min(int i, int j) {
		return i > j ? j : i;
	}
}