[分析]
暴力的办法就是从1开始检查每个数是否是丑数,发现丑数计数器加1直到找到第n个丑数。这种方法效率低,因为它不管是不是丑数都进行了计算,所以优化方向是仅计算丑数而不在非丑数上耗费时间。易知后面的丑数一定是前面的丑数乘以2或者3或者5得到的,假设现在已经计算出第k个丑数U(k),那么下一个丑数是前面丑数中乘以2、3、5中第一个大于U(k)的数。怎么找呢?我们需要保留已计算的所有丑数,将已知丑数逐个乘2并同U(k)比较,第一个大于U(k)的数记为next2, 同样的方式计算出next3, next5, 下一个丑数就是next2, next3, next5三者间的最小值。每次必须从第一个丑数开始找吗?不是的,可以进一步优化,对乘以2而言,肯定存在某个丑数T2, 其前的丑数乘2小于U(k), 其以后的都大于U(k), 记录T2所在位置,每次生成新丑数时更新该位置,对乘以3和乘以5同样记录相应位置。
[ref]
https://leetcode.com/discuss/52716/o-n-java-solution
public class Solution {
public int nthUglyNumber(int n) {
int[] uglyNum = new int[n];
uglyNum[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
int next2 = 2, next3 = 3, next5 = 5;
for (int i = 1; i < n; i++){
uglyNum[i] = Math.min(Math.min(next2, next3), next5);
if (uglyNum[i] == next2) {
next2 = uglyNum[++p2] * 2;
}
if (uglyNum[i] == next3) {
next3 = uglyNum[++p3] * 3;
}
if (uglyNum[i] == next5) {
next5 = uglyNum[++p5] * 5;
}
}
return uglyNum[n-1];
}
}
分享到:
相关推荐
1201.Ugly-Number-III(待定) (H) (男) (H) Binary Search by Value (男) (H-) (H-) (H) (H-) (H-) (H) (H-) (H-) (H) (H-) (H-) (男) (男) (H-) (M+) (男) (M+) (男) (M+) (H-) (M+
leetcode leetcode-java leetcode刷题笔记 已做题目列表 1.Two Sum 3.Longest Substring Without Repeating Characters 5.Longest Palindromic Substring 20.Valid Parentheses 26.Remove Duplicates from Sorted ...
super_ugly_number.cpp - Detect_Pattern.cpp - degree_of_array.cpp - 键盘.cpp - 2Sum_Data_Structure_Design.cpp - shuffle_array.cpp - permutations.cpp - kth_missing_number.cpp - 3sum2.cpp - 3sum.cpp - ...
137 | [Single Number II](https://leetcode.com/problems/single-number-ii/) | [C++](./C++/single-number-ii.cpp) [Python](./Python/single-number-ii.py) | _O(n)_ | _O(1)_ | Medium ||| 190 | [Reverse Bits]...
高效算法的奥秘》 /《黑客的喜悦》,第二版《数学之美》(吴君医生的中文译本) 《编程之美:微软技术面试心得》(Mircosoft Developers的中文版)Leetcode数学问题解时间空间困难注意263.ugly-number ,O(1) O(1...
leetcode伪代码LeetCode 难题代码和算法要点...1201.Ugly-Number-III(待定) (H) (男) (H) Binary Search by Value (男) (H-) (H-) (H) (H-) (H-) (H) (H-) (H-) (H) (H-) (H-) (男) (男
leetcode最大蓄水量 leetcode 记录自己leetocde的过程 2021.1.31 496 Next Greater Element I 复习了 linkedlist,arraylist的区别 ...Number II 三指针 2 3 5 2021.2.5 105 ConstructBinaryTreefromPreorderandI
Ugly Number II Super Ugly Number Fraction to Recurring Decimal Factorial Trailing Zeroes Nim Game 模拟 Reverse Integer Palindrome Number Insert Interval Merge Intervals Minimum Window Substring ...
分解输入的值,如果质数仅含2,3,5,则为UglyNumber 6 给一个股票价格数组,数组中为整型数字,你可以选一天买入股票,可以后面的某天售出,问你能赚的最大利润 7 判断是否为HappyNumber,输入一个数,将该数的各个...
山中阵列(TBD) (H-) 1201.Ugly-Number-III(TBD) (H) (M) (H) Binary Search by Value (M) (H-) (H-) (H) (H-) (H-) (H) (H-) (H-) (H) (H-) (H-)(M) (M) (H)
java lru leetcode ##Thinking in Java chapter21 ##Netty in Action ####chapter2: echo server/client ##数据结构与算法 ...##leetcode ...[Ugly Number] ...[Ugly Number II] () [Repeated DNA Sequences] () [Lar