这是剑指第一次卡死我的题……记录一下
首先看题目：
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
一开始的思路：
一开始，我就直接蛮力，就按照它的描述，从2到根号n一个个试，看看是不是它的因子，是的话是不是质数，是质数的话是不是2或者3或者5什么的。
最后做出来，前面几个数字都是可以通过测试的，但提交就一直说我超时通过率为0……然后本地测了下超时的用例1500——emmm确实是，算了半天都没出来。
然后百度，百度百科上对丑数的判别：
链接：https://www.nowcoder.com/questionTerminal/6aa9e04fc3794f68acf8778237ba065b
来源：牛客网
然后我按照这个思路，自己实现了次，也遇到了很多问题……
我是真正地维护了三个队列，然后每次把最新的丑数乘以2，3，5然后分别加到三个队列中，然后取出最小的数字处理，从哪个队列中取出就哪个队列出队。队列直接用PriorityQueue，可以直接获得最小值。
遇到的问题是：
1. 我这个直接按照上面的思路做的话，到后面数字很大会溢出……然后溢出的话，比如一个很大的丑数*5溢出了，就变成一个负数然后以后的最小值就是这个负数了——我的解决方法是：重写一个Compator，然后传入PriorityQueue中去。
2. 这还不够，因为到了后面，可能出现一个队列中的所有数字都小于0的情况，所以在拿出数字后比较出最小的这一步也要考虑到负数的情况。
看下我的这个思路的实现的代码，已经通过测试：
import java.util.*;
public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index <= 0)return 0;
if(index == 1)return 1;
Queue<Integer> q2 = new PriorityQueue<Integer>(new NewComparator());
Queue<Integer> q3 = new PriorityQueue<Integer>(new NewComparator());
Queue<Integer> q5 = new PriorityQueue<Integer>(new NewComparator());
int uglyNum = 1, count = 1, minTemp;
while(true) {
q2.add(uglyNum * 2);
q3.add(uglyNum * 3);
q5.add(uglyNum * 5);
//下面的操作这么麻烦是因为会有几个队列有着同样的最小值的情况，这时候都要让它出队
minTemp = getMinOfThree(q2.peek(), q3.peek(), q5.peek(), count);
if(q2.peek() == minTemp)q2.poll();
if(q3.peek() == minTemp)q3.poll();
if(q5.peek() == minTemp)q5.poll();
uglyNum = minTemp;
count++;
if(count == index)return uglyNum;
}
}
// 找三个数字中没有溢出的最小值
private int getMinOfThree(int a, int b, int c, int count) {
if (a < 0 || b < 0 || c < 0) {// 存在溢出情况，有元素小于0
int[] temp = new int[3];
temp[0] = a;
temp[1] = b;
temp[2] = c;
Arrays.sort(temp);
for (int x : temp) {
if (x < 0)
continue;
return x;
}
}
return a < b ? (a < c ? a : c) : (b < c ? b : c);
}
//因为之前的那个，如果有数字溢出了，就会变成负数，负数肯定最小然后就会被poll出来，最后结果就会有错误
private class NewComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
if(o1 < 0)return 1;
if(o1 < o2)return -1;
else if(o1 == o2)return 0;
else return 1;
}
}
}但其实我们可以不用维护三个队列：
链接：https://www.nowcoder.com/questionTerminal/6aa9e04fc3794f68acf8778237ba065b
来源：牛客网
public int GetUglyNumber_Solution2(int index) {
if (index <= 0)
return 0;
ArrayList<Integer> list = new ArrayList<Integer>();
// add进第一个丑数1
list.add(1);
// 三个下标用于记录丑数的位置
int i2 = 0, i3 = 0, i5 = 0;
while (list.size() < index) {
// 三个数都是可能的丑数，取最小的放进丑数数组里面
int n2 = list.get(i2) * 2;
int n3 = list.get(i3) * 3;
int n5 = list.get(i5) * 5;
int min = Math.min(n2, Math.min(n3, n5));
list.add(min);
if (min == n2)
i2++;
if (min == n3)
i3++;
if (min == n5)
i5++;
}
return list.get(list.size() - 1);
}可以看见，就是三个指针在动。而且这里似乎不会出现溢出有负数的情况，因为我那里每次是用最新的丑数去乘2，3，5；而这里是用之前的丑数，就i2，i3，i5指针所在的那个丑数来乘，所以好很多。