[剑指 Offer 第 2 版第 49 题] “丑数”做题记录-Java极客技术学习

[剑指 Offer 第 2 版第 49 题] “丑数”做题记录

第 49 题：丑数

把只包含因子 $2$ 、 $3$ 和 $5$ 的数称作丑数（Ugly Number）。

例如 $6$ 、 $8$ 都是丑数，但 $14$ 不是，因为它包含因子 $7$ 。

求按从小到大的顺序的第 $N$ 个丑数。

样例：

输入：5

输出：5

注意：习惯上我们把 $1$ 当做是第一个丑数。

同 LeetCode 第 264 题，题解传送门：LeetCode 上的丑数问题。

思路：所谓的一个数 $m$ 是另一个数 $n$ 的因子，是指 $n$ 能被 $m$ 整除，也就是 $n\\%m==0$ 成立。根据丑数的定义，丑数只能被 $2$ 、 $3$ 和 $5$ 整除。根据丑数的定义，丑数应该是另一个丑数乘以 $2$ 、 $3$ 或者 $5$ 的结果（ $1$ 除外）。因此我们可以创建一个数组，里面的数字是排好序的丑数，每一个丑数都是前面的丑数乘以 $2$ 、 $3$ 或者 $5$ 得到的。

这个思路的关键问题在于怎样保证数组里面的丑数是排好序的。对乘以 $2$ 而言，肯定存在某一个丑数 $T2$ ，排在它之前的每一个丑数乘以 $2$ 得到的结果都会小于已有最大的丑数，在它之后的每一个丑数乘以乘以 $2$ 得到的结果都会太大。我们只需要记下这个丑数的位置，同时每次生成新的丑数的时候，去更新这个 $T2$ 。对乘以 $3$ 和 $5$ 而言，也存在着同样的 $T3$ 和 $T5$ 。

Python 代码：

  class Solution:
        def GetUglyNumber_Solution(self, index):
            # write code here
            if index < 7:
                return index
            res = [1, 2, 3, 4, 5, 6]
            t2, t3, t5 = 3, 2, 1
            for i in range(6, index):
                res.append(min(res[t2] * 2, min(res[t3] * 3, res[t5] * 5)))
                while res[t2] * 2 <= res[i]:
                    t2 += 1
                while res[t3] * 3 <= res[i]:
                    t3 += 1
                while res[t5] * 5 <= res[i]:
                    t5 += 1
            return res[index - 1]

Java 代码：

  public class Solution2 {

        // 1、2、3、4、5、6 都是丑数
        public int GetUglyNumber_Solution(int index) {
            if (index < 7) {
                return index;
            }

            // 状态的定义：第 i 个丑数的最小值，从 0 开始计算
            int[] dp = new int[index];
            dp[0] = 1;

            int t2 = 0;
            int t3 = 0;
            int t5 = 0;

            // 注意： i 从 1 开始
            for (int i = 1; i < index; i++) {
                dp[i] = min3(dp[t2] * 2, dp[t3] * 3, dp[t5] * 5);
                if (dp[i] == dp[t2] * 2) {
                    t2++;
                }
                if (dp[i] == dp[t3] * 3) {
                    t3++;
                }
                if (dp[i] == dp[t5] * 5) {
                    t5++;
                }
            }
            // System.out.println(Arrays.toString(dp));
            return dp[index - 1];
        }

        private int min3(int n1, int n2, int n3) {
            return Integer.min(Integer.min(n1, n2), n3);
        }

        public static void main(String[] args) {
            Solution2 solution2 = new Solution2();
            // 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24
            // [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
            int getUglyNumberSolution = solution2.GetUglyNumber_Solution(15);
        }
    }