丑数

题目描述

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

解题思路

• list 内根据顺序保存已有的丑数；

• 定义 2,3,5 的 index，比较与 index 上的数的乘积的大小：

• 最小值加入 list 内，并且相应的 index++。

代码

import java.util.ArrayList;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if (index <= 0)
            return 0;
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        int index2 = 0;
        int index3 = 0;
        int index5 = 0;
        for (int i = 1; i < index; i++) {
            int tmp2 = list.get(index2) * 2;
            int tmp3 = list.get(index3) * 3;
            int tmp5 = list.get(index5) * 5;
            int min = Math.min(tmp2, Math.min(tmp3, tmp5));
            list.add(min);
            if (tmp2 == min)
                index2++;
            if (tmp3 == min)
                index3++;
            if (tmp5 == min)
                index5++;
        }
        return list.get(index-1);
    }
}