企业网站建设的目的,企业大型网站开发设计建站流程,常山做网站,国外优秀的html5网站考察点
空间换时间提效知识点
题目
分析 这里面其实用到了一点点的数学知识#xff0c;丑数的定义是只包含2#xff0c;3#xff0c;5因子的数。现在要求第1500个丑数#xff0c;最简单的办法就是从数字1开始遍历#xff0c;依次判断每个数字是不是丑数#xff0c;如果…考察点
空间换时间提效知识点
题目
分析 这里面其实用到了一点点的数学知识丑数的定义是只包含235因子的数。现在要求第1500个丑数最简单的办法就是从数字1开始遍历依次判断每个数字是不是丑数如果是的话累计丑数数量直到1500而判断是否是丑树的办法就是依次求余235并且除235最后数字是1的话则说明它是丑数这种方法时间复杂度非常非常的高针对非丑数它也会计算一次。我们需要想一个高效的算法这里同样用到一点数学知识按照题目的定义丑数一定是丑数的23或者5倍所以可以看出最新的丑数和历史的丑数是有关系的所以我们其实可以把历史的丑数都存起来每次在求新的丑数的时候都求一遍历史丑数的235倍并且取这里面的最小值就是最新的丑数(前提是不能重复)。这里面又有一个问题每次都求一遍历史的所有数据的2,3,5倍也很耗时其实只要我们存起来的丑数是按照顺序存放的那么可以把每次不超过最新丑数的最大元素的下标存起来每次只要取这3个元素的最小值就可以了因为由于顺序存放所以比最大元素小的那些元素的235倍的数据一定已经存在了
public class ThirtyFour {public static void main(String[] args) {
// System.out.println(uglyOne(1500));System.out.println(ugly(1500));}public static long ugly(int length) {int index 1;long[] arr new long[length];arr[0] 1;int twoIndex 0;int threeIndex 0;int fiveIndex 0;while(index length) {long val min(arr[twoIndex] * 2,arr[threeIndex] * 3,arr[fiveIndex] * 5);arr[index] val;while(arr[twoIndex] * 2 arr[index]) {twoIndex;}while(arr[threeIndex] * 3 arr[index]) {threeIndex;}while(arr[fiveIndex] * 5 arr[index]) {fiveIndex;}index index 1;}return arr[length - 1];}public static long min(long a,long b,long c) {if (a b) {if (a c) {return a;} else {return c;}} else {if (b c) {return b;} else {return c;}}}public static long uglyOne(int length) {int data 1;int count 0;while(count length) {int i data;while(i % 2 0) {i / 2;}while(i % 3 0) {i / 3;}while(i % 5 0) {i / 5;}if (i 1) {count;}data;}return data - 1;}
}
