2021.4.11

264. 丑数II

https://leetcode-cn.com/problems/ugly-number-ii/
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。

提示：
1 <= n <= 1690

学到的知识点：动态规划
明天写，或者后天
我写的：（C#）

public class Solution {
    public int NthUglyNumber(int n) {
            int index = 0;
            int max2 = Int32.MaxValue / 2;
            int max3 = Int32.MaxValue / 3;
            int max5 = Int32.MaxValue / 5;
            SortedList sortedList = new SortedList();
            sortedList.Add(1, 0);
            while (index < n + 1)
            {
                int i = (int)sortedList.GetKey(index);
                if (!sortedList.ContainsKey(i * 2) && i < max2) sortedList.Add(i * 2, 0);
                if (!sortedList.ContainsKey(i * 3) && i < max3) sortedList.Add(i * 3, 0);
                if (!sortedList.ContainsKey(i * 5) && i < max5) sortedList.Add(i * 5, 0);
                index++;
            }
            return (int)sortedList.GetKey(index - 2);
    }
}

运行时间击败了10%，针不戳
你可少玩点SortedList吧
学来的：

public class Solution {
    public int NthUglyNumber(int n) {
        int[] dp = new int[n];
        int p2 = 0, p3 = 0, p5 = 0;
        dp[0] = 1;
        for (int i = 1; i < n; i++)
        {
            dp[i] = Math.Min(Math.Min(dp[p2] * 2, dp[p3] * 3), dp[p5] * 5);
            if (dp[i] == dp[p2] * 2) p2++;
            if (dp[i] == dp[p3] * 3) p3++;
            if (dp[i] == dp[p5] * 5) p5++;
        }
        return dp[n - 1];
    }
}

真优雅。