• 丑数
    • 解题思路

    丑数

    牛客网

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

    解题思路

    1. 通过保存已有丑数的方式，用空间换时间
    2. 对于已有丑数 $$M$$ ，那么下一个丑数 $$M=\min(M{2}\times2,M{3}\times3,M_{5}\times5)$$
    3. $$M{max}$$ 是目前最大的丑数，那么 $$M{2}$$ 是已有丑数中 $$M{2}\times2$$ 第一个大于 $$M{max}$$ 的丑数
    1. public int GetUglyNumber_Solution(int index) {
    2.     if (index == 0) {
    3.         return 0;
    4.     }
    6.     if (index == 1) {
    7.         return 1;
    8.     }
    10.     ArrayList<Integer> list = new ArrayList<>(index);
    11.     list.add(1);
    13.     int preIndex2 = 0;
    14.     int preIndex3 = 0;
    15.     int preIndex5 = 0;
    16.     for (int i = 0; i < index; i++) {
    17.         int next2 = list.get(preIndex2) * 2;
    18.         int next3 = list.get(preIndex3) * 3;
    19.         int next5 = list.get(preIndex5) * 5;
    21.         int nextV = Math.min(Math.min(next2, next3), next5);
    22.         list.add(nextV);
    24.         while (preIndex2 < list.size() - 1 && list.get(preIndex2) * 2 <= nextV) preIndex2++;
    25.         while (preIndex3 < list.size() - 1 && list.get(preIndex3) * 3 <= nextV) preIndex3++;
    26.         while (preIndex5 < list.size() - 1 && list.get(preIndex5) * 5 <= nextV) preIndex5++;
    27.     }
    29.     return list.get(index - 1);
    30. }