微信端网站设计规范,官网申请,买手机的网站,个人做免费网页题目信息
LeetoCode地址: . - 力扣#xff08;LeetCode#xff09;
题目理解
所谓丑数就是满足: (2^x)*(3^y)*(5^z), 其中,x,y,z 0的数。
题目要求的是求严格递增的第n个丑数。
最小堆写法
可以维护一个小顶堆#xff0c;每一次拿出堆顶元素#xff0c;然后分别…题目信息
LeetoCode地址: . - 力扣LeetCode
题目理解
所谓丑数就是满足: (2^x)*(3^y)*(5^z), 其中,x,y,z 0的数。
题目要求的是求严格递增的第n个丑数。
最小堆写法
可以维护一个小顶堆每一次拿出堆顶元素然后分别乘以235再都扔回堆里依次进行操作直到第n个元素。在实现时要注意对重复元素的处理。
时间复杂度:(nlogn),堆的每次出入操作需要花费logn, 共需要n次这样的操作。
额外空间复杂度: (n) 我们需要维护一个最大长度为n的堆。
class Solution {public int nthUglyNumber(int n) {int[] factors {2, 3, 5};SetLong seen new HashSetLong();PriorityQueueLong heap new PriorityQueueLong();seen.add(1L);heap.offer(1L);int ugly 0;for (int i 0; i n; i) {long curr heap.poll();ugly (int) curr;for (int factor : factors) {long next curr * factor;if (seen.add(next)) {heap.offer(next);}}}return ugly;}
}
动态规划写法
第k个丑数一定是它之前的0到k-1之间某一个更小的的丑数乘以2或3或5得到的我们要找的就是其中乘完后刚好最小同时又大过k-1丑数的数。
既然如此可以使用三个下标x,y,z分别记录还未被235乘过的丑数。
每一次计算第k个丑数时将第x个丑数乘以2第y个丑数乘以3第z个丑数乘以5得到的最小值就是第k个丑数。假设第x个丑数乘以2是最小的则将x1,因为第x个丑数已经乘过2并用过了。y和z类似。
时间复杂度: O(n)
空间复杂度: O(n)
static int[] dp new int[1691];public int nthUglyNumber(int n) {if (dp[0] 0) {dp[1] 1;int x1,y1,z1;for (int i 2; in; i) {int xMin dp[x] *2;int yMin dp[y] *3;int zMin dp[z] * 5;int min Math.min(xMin, Math.min(yMin, zMin));if (min xMin) {x;}if (min yMin) {y;}if (min zMin) {z;}dp[i] min;}}return dp[n];}
