网站嵌入视频代码,广东万高建设网站,高端网站开发培训,笔记本网站开发背景问题描述#xff1a;我们只把包含因子2、3和5的数称为丑数。求按从小到大的顺序的第1500个丑数。 分析#xff1a;要找到第i个丑数#xff0c;需要用辅助数组存储前面i-1个丑数#xff0c;用空间换取时间。 package com.wyl;
/*** 求丑数* 问题描述#xff1a;我们只把包含…问题描述我们只把包含因子2、3和5的数称为丑数。求按从小到大的顺序的第1500个丑数。 分析要找到第i个丑数需要用辅助数组存储前面i-1个丑数用空间换取时间。 package com.wyl;
/*** 求丑数* 问题描述我们只把包含因子2、3和5的数称为丑数。求按从小到大的顺序的第1500个丑数。* author wyl**/
public class UglyNumber {/*** 得到第number个丑数* param number* return*/public int getUglyNumber(int number){int[] uglyNumbers new int[number]; //用来存储丑数uglyNumbers[0] 1; //第一个丑数为1int nextUglyIndex 1; //控制给uglyNumbers数组存储丑数的下标int uglyNumber2 0; //记录乘以2的指针int uglyNumber3 0; //记录乘以3的指针int uglyNumber5 0; //记录乘以5的指针while(nextUglyIndex number){//要存储的丑数必须是uglyNumber2*2、uglyNumber3*3和uglyNumber5*5中最小的数//并且更新uglyNumber2、uglyNumber3和uglyNumber5的指针//保证存在某个丑数使得要存储的丑数左边的丑数*2都比它 小右边的*2都比它大//保证存在某个丑数要存储的丑数左边的丑数*3都比它 小右边的*3都比它大//保证存在某个丑数要存储的丑数左边的丑数*5都比它 小右边的*5都比它大int min Min(uglyNumbers[uglyNumber2] * 2, uglyNumbers[uglyNumber3] * 3, uglyNumbers[uglyNumber5] * 5);uglyNumbers[nextUglyIndex] min;while(uglyNumbers[uglyNumber2] * 2 uglyNumbers[nextUglyIndex]){uglyNumber2; //移动乘2的指针}while(uglyNumbers[uglyNumber3] * 3 uglyNumbers[nextUglyIndex]){uglyNumber3; //移动乘3的指针}while(uglyNumbers[uglyNumber5] * 5 uglyNumbers[nextUglyIndex]){uglyNumber5; //移动乘5的指针}nextUglyIndex;}return uglyNumbers[number-1];}//求三个整数中的最小值private int Min(int i, int j, int k) {// TODO Auto-generated method stubint min ij?i:j;min (min k)?min:k;return min;}public static void main(String[] args) {UglyNumber uglyNumber new UglyNumber();int uNumber uglyNumber.getUglyNumber(10);System.out.println(第1500个丑数为 uNumber);}
} 转载于:https://www.cnblogs.com/studyDetail/p/7238828.html
