剑指Offer——丑数
前言
参照《剑指Offer》，通过洞悉其思想并消化吸收，改为java实现，供自己以后巩固。
package cn.edu.ujn.offersword;
import java.util.Scanner;
public class C5_34_UglyNumber {
/**
* @date 2016-09-16
* @number 01
* @author SHQ
* 丑数
* 题目描述
*把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
* 思路
*空间换时间
*根据丑数的定义，丑数应该是另一个丑数乘以2，3，或5所得(1除外)。故非丑数不在计算范围之内。额外创建一个数组，用于存放已确定的丑数。
*通过设置3个变量，用于标记第一个大于最大丑数的位置，并将3个变量中的最小丑数作为下一个丑数。 同时避免重复计算。
* 空间复杂度O(n);
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNextInt()){
int index = in.nextInt();
System.out.println(GetUglyNumber_Solution2(index));
}
}
// 超时
private static int GetUglyNumber_Solution(int index) {
if(index <= 0){
return 0;
}
int cnt = 0;
int number = 1;
while(cnt < index){
if(isUgly(number)){
cnt++;
}
number++;
}
return number;
}
private static boolean isUgly(int num){
while(num % 2 == 0)
num /= 2;
while(num % 3 == 0)
num /= 3;
while(num % 5 == 0)
num /= 5;
return num == 1 ? true : false;
}
private static int GetUglyNumber_Solution2(int index) {
if(index <= 0){
return 0;
}
int [] arr = new int [index];
arr[0] = 1;
int index2 = 0, index3 = 0, index5 = 0, nextIndex = 1;
while(nextIndex < index){
System.out.print(arr[nextIndex-1] + " ");
int min = min(arr[index2]*2, arr[index3]*3, arr[index5]*5);
arr[nextIndex] = min;
while(arr[index2] * 2 <= arr[nextIndex])
index2++;
while(arr[index3] * 3 <= arr[nextIndex])
index3++;
while(arr[index5] * 5 <= arr[nextIndex])
index5++;
nextIndex++;
}
return arr[nextIndex-1];
}
private static int min(int a, int b, int c){
int min = (a > b) ? b : a;
return min > c ? c : min;
}
}