丑数求解以及丑数的优化 阳光穿透心脏的1/2处 2022-06-09 09:55 249阅读 0赞 #### 丑数: #### **丑数是指因子只有2,3,5的数** **比如 6 因子2,3** **比如 15 因子3,5** **另外特别的,规定1为丑数** 求第K个丑数? 最近在刷剑指offer的OJ时,在查找丑数的时候出现了超时的情况,特别记录下来优化的找法。 ##### 第一种解法: ##### 循环数字,为丑数时index+1,直到index==k public static void find(int index){ ArrayList<Integer> list = new ArrayList<Integer>(index); int i=1; while(list.size()!=index){ if(judgeUglySum(i)) list.add(i); i++; } System.out.println(list.get(list.size()-1)); } /*** * 消去所有丑数因子 * @param i 判断i是否是丑数 * @return */ private static boolean judgeUglySum(int i) { while(i%2==0){ //i/=2; i=i>>1; //除2 可以改为右移2 } while(i%3==0){ i/=3; } while(i%5==0){ i/=5; } if(i==1){ return true; } return false; } 这种的解法的缺点在于每次所有的数进行遍历(其中丑数只占一部分),在遍历更大都数字时会出现查找十分费时。仅仅index==1500,数字达到了8亿左右,耗时8秒; ##### 从丑数中找丑数 ##### 下一步便是想办法从因子中找到最小的丑数 我的思维:想从因子得乘积判断最小值判断 ,发现 所以关键在于2,3,5乘什么; 1 1*2=2 1*3=3 1*5=5 2*2=4 2*2*2=8 3*2 =6 解决办法是用index2,index3,index5记录上次乘的下标; public static void find2(int index){ if(index<0){ return -1; } if(index<7){ // 1-6 都是丑数 return index; } int[] array = new int[index]; array[0]=1; //用于记录2,3,5乘到哪一位了 int index2 = 0,index3 = 0,index5 = 0; for(int i=1;i<index;i++){ int tmp=array[index3]*3<array[index5]*5?array[index3]*3:array[index5]*5; array[i]=array[index2]*2<tmp?array[index2]*2:tmp; if(array[i]==array[index2]*2) index2++; //表明这次是选的2 if(array[i]==array[index3]*3) index3++; if(array[i]==array[index5]*5) index5++; } System.out.println(array[index-1]); //return array[index-1]; } 改良之后算第1500个丑数的时候,零毫秒。 ps:但是会出现数字超出int范围的情况,在K=1692时丑数的时候就超出了整数的范围。 算出从1到K=1692时,总共才费时34ms,和原来的8s相比天壤之别; 这优化简直了,真的很佩服! 总结: 经过这次的练习让我觉得小的事情上还有如此多的玄机,连找个丑数这种看似很简单的问题,我最开始也没找到思路,最开始我就想在因子里面找,但是没想出来到底乘那个数字,因为最开始2最小,一直乘2也会变大。 后来开始看第一种解法,循环求余,除去因子,最后判断结果是否为1。 第二种解法,还是很巧妙的。
相关 丑数 一、题目大意 只包含因子2、3、5的数叫丑数,习惯上把1也看做丑数,求第1500个丑数。 二、分析 (1)常规做法,可对每个正整数依次遍历,直到找到第1500个丑数为止。 小咪咪/ 2023年11月20日 07:29/ 0 赞/ 135 阅读
相关 丑数 ![在这里插入图片描述][20200302095046787.png] include<stdio.h> int main() { int 朱雀/ 2023年07月10日 11:19/ 0 赞/ 152 阅读
相关 丑数 把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个 矫情吗;*/ 2023年02月18日 08:16/ 0 赞/ 21 阅读
相关 丑数 \\题目描述 把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到 r囧r小猫/ 2022年10月27日 13:48/ 0 赞/ 194 阅读
相关 丑数求解以及丑数的优化 丑数: 丑数是指因子只有2,3,5的数 比如 6 因子2,3 比如 15 因子3,5 另外特别的,规定1为丑数 求第K个丑数? 最近在刷剑指offer的 阳光穿透心脏的1/2处/ 2022年06月09日 09:55/ 0 赞/ 250 阅读
相关 丑数 把只包含因子2、3和5的数称作丑数,例如6,8都是丑数,但14不是,因为它包含因子7,习惯上我们把1当作第一个丑数,求按从小到大的顺序的第N个丑数。 输入描述:整数N 小咪咪/ 2022年06月08日 08:52/ 0 赞/ 236 阅读
相关 丑数 求第1500个丑数。丑数是不能被2.3.5之外的其他素数整除的数,把丑数从小到大排起来,然后打印第1500个 先写一个典例,我写的, //这是我写的,运行了大概15 你的名字/ 2022年05月18日 10:55/ 0 赞/ 203 阅读
相关 丑数 时间限制:1秒 空间限制:32768K 热度指数:223966 本题知识点: 数组 算法知识视频讲解 题目描述 把只包含质因子2、3和5的数称作丑数(Ugly 本是古典 何须时尚/ 2022年03月09日 10:50/ 0 赞/ 287 阅读
相关 丑数 列表res按序存储丑数 res\[0\] = 1, 下一个丑数产生规则: 1.找出res所有数\2 中第一个 大于 res \[-1\] 的数:res\[n2\] 2 迷南。/ 2022年01月30日 07:43/ 0 赞/ 250 阅读
相关 丑数 丑数就是只包含质因数 2, 3, 5 的正整数。 1.判断丑数 2.找到第n个丑数 (代码很容易看懂) public class UglyNum { 梦里梦外;/ 2021年09月26日 23:24/ 0 赞/ 349 阅读
还没有评论,来说两句吧...