面试题34. 丑数
题目描述
把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0gTMx81dsQWZ4lmZf1GLlpXazVmcvwFciV2dsQXYtJ3bm9CX9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cGcq5SN2gDM1U2Y5UGOidDOhRDMzYzX5EDNxgTMzIzLchDMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.jpg)
思路:
丑数应该是另一个丑数乘以2、3、5得到的。也就是说,根据一个丑数,可以计算出它乘以2、3、5得到的丑数。因此,可以初始化一个数组arr,用于保存已经找到的丑数。然后按序用数组里的数,乘以2、3、5得到新的丑数,并加入到数组中。
public class Solution
public int GetUglyNumber_Solution(int n) {
if(n <= 0) return 0;
int[] arr = new int[n];
arr[0] = 1;
int i = 0, j = 0, k = 0; // 分别代表2,3,5的下标
for(int a = 1; a < n; a++) {
int p = arr[i] << 1;
int q = arr[j] * 3;
int r = arr[k] * 5;
int min = Math.min(p, Math.min(q, r));
arr[a] = min;
if(p == min) {
i++;
}
if(q == min) {
j++;
}
if(r == min) {
k++;
}
}
return arr[n-1];
}
}