题目:我们把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。
思路:
只计算丑数,而不在非丑数的整数上花费时间。根据丑数的定义,丑数应该是另一个丑数乘以2、3或者5的结果(1除外)。因此我们可以创建一个数组,里面的数字是排好序的丑数。里面的每一个丑数是前面的丑数乘以2、3或者5得到的。
1,2,3,5,2*2,2*3,2*5,3*2,3*3,3*5,5*2(重复),5*3,5*5.....
使用LinkedHashMap来弄,把他当做队列
LinkedHashMap list = new LinkedHashMap();
list.add(1);
int[] arr = new int[]{2,3,5};
int arrIndex = 0;
public void getUglyNumber(int count){
while(list.size()<count){
list.add(list.get(listIndex)*arr[listIndex%3]);
listIndex++;
}
System.out.println(list.get(count));
}
分享到:
相关推荐
程序员面试题精选100题
程序员面试题精选100题
程序员面试题精选程序员面试题精选程序员面试题程序员面试题精选精选
程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试...
程序员面试题精选100题-何海涛 程序员 面试题 算法 数据结构
程序员面试题精选100题(2008)程序员面试题精选100题(2008)
程序员面试题精选100题
一份可以让大家在求职时更能自信的题解,经典的100题,让大家可以感受到算法的经典,当然,自己要更加努力,要懂得举一反三才能更上一层楼!
程序员面试题精选100题
------------------------------------- java程序员早期面试题汇总 BAT经典面试题汇总.pdf Java常考面试题.pdf java面试题(题库全)....程序员面试题精选100题.pdf ... -------------------------------------
程序员面试题精选100题,以前下过的不全,自己在网上搜了搜,整理了一下。