剑指 Offer 49. 丑数

题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

解题思路

• 由于只含质因子2，3，5，那么可以知道，每一个丑数都是由这三个数互相做乘法而来的。
• 我们定义三个指针n2Index，n3Index，n5Index，每一次只需要比较n2Index * 2，n3Index * 3，n5Index * 5，拿到最小的那一个，更新为下一个丑数。将最小的那个指针下标 n*Index + 1。

class Solution {
    public int nthUglyNumber(int n) {
        int n2Index = 0;
        int n3Index = 0;
        int n5Index = 0;
        final ArrayList<Integer> ugly = new ArrayList<>();
        ugly.add(1);
        for (int i = 1; i < n; i++) {
            int n2 = ugly.get(n2Index) * 2;
            int n3 = ugly.get(n3Index) * 3;
            int n5 = ugly.get(n5Index) * 5;
            int min = Math.min(Math.min(n2, n3), n5);
            if (n2 == min) n2Index++;
            if (n3 == min) n3Index++;
            if (n5 == min) n5Index++;
            ugly.add(min);
        }
        return ugly.get(n - 1);
    }
}