剑指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; } }