Leetcode丑数题解

Leetcode丑数题解

背景

年初时参加了一场面试，第一轮比较顺利，英文聊了将近一个小时技术，外加做了两道coding题目。第二轮遇到一个求丑数的题目，其实这道题明明是做过的Leetcode原题，无奈已经不记得具体思路，结果非常痛心。

题目

题目是这样的：

给你一个整数 n ，请你找出并返回第 n 个 丑数 。丑数 就是只包含质因数 2、3 和/或 5 的正整数。

最近痛定思痛，用了两种方法解决：

1. 小顶堆

思路

因为每次需要按照由小到大的顺序生成，所以最先想到的是可以利用小顶堆自然排序的特性依次取出最小的丑数，然后再用该数字与给出的质因数相乘得到下一个丑数，但过程中需要去重，即当前丑数只能与大于等于该丑数的最大质因数的数字相乘得到下一个丑数。

实现

public int nthUglyNumber(int n) {PriorityQueue<Long> queue = new PriorityQueue<>();int[] uglys = {5, 3, 2};queue.offer(1L);long curr = 0;while (n-- > 0) {curr = queue.poll();for (int ugly : uglys) {queue.offer(curr * ugly);if (curr % ugly == 0) break;//剪枝，去重}}return (int) curr;
}

复杂度

时间复杂度：O(nlogn)
空间复杂度：O(n)

2. 动态规划

思路

在一些丑数质因数比较多的场景下，小顶堆的方法会超时，所以需要一种性能更优的方法来实现：

数组dp[i]：表示第i个丑数；
数组uglys[i]：生成丑数的质因数；
下一个丑数 = min(丑数质因数 * 已生成的某个丑数)，所以需要定义一个数组用来作为指向这个已生成丑数的指针；
数组pointers[i]：指向丑数生成序列中的已生成的某个丑数的指针，初始化为0；
数组nums[i]：下一个丑数备选集合，即，nums[i] = uglys[i] * dp[pointers[i]]；每次计算得到nums，并从该集合数组中选出最小的元素；一旦元素被选中成为下一个丑数，需要更新pointers[i]（自增1，代表指向下一个丑数），nums[i] = uglys[i] * dp[pointers[i]];
最小的丑数是1，将nums[i]初始化为1

实现

public int nthUglyNumber(int n) {long[] dp = new long[n + 1];int[] uglys = {5, 3, 2};int[] pointers = new int[uglys.length];long[] nums = new long[uglys.length];Arrays.fill(nums, 1L);for (int i = 1; i <= n; i++) {long min = Arrays.stream(nums).min().getAsLong();dp[i] = min;for (int j = 0; j < uglys.length; j++) {if (nums[j] == min) {pointers[j]++;nums[j] = dp[pointers[j]] * uglys[j];}}}return (int) dp[n];
}

复杂度

时间复杂度：O(nm)
空间复杂度：O(n + m)
m是丑数素因子个数，改题目中为3

3. 性能对比

再验证下两种方法对比，可见内存消耗基本一致，动态规划的性能提升的确非常明显：

复盘

这道题目的小顶堆是中等难度，为什么当时连思路都没想清楚？虽然用面试长达3个小时时出现，感觉脑子转不动了来安慰自己，但究其根本还是自己当时在Leetcode做这道题时，也就是做出来就算了，只想着速战速决，没有花时间进行深入思考和分析，本来就有欠账。今天专门找到了动态规划的解法，的确性能提升很多。