剑指offer面试题34 丑数

考察点

空间换时间提效

知识点

题目

分析
这里面其实用到了一点点的数学知识，丑数的定义是只包含2，3，5因子的数。现在要求第1500个丑数，最简单的办法就是从数字1开始遍历，依次判断每个数字是不是丑数，如果是的话累计丑数数量直到1500，而判断是否是丑树的办法就是依次求余2，3，5，并且除2，3，5，最后数字是1的话则说明它是丑数，这种方法时间复杂度非常非常的高，针对非丑数它也会计算一次。我们需要想一个高效的算法，这里同样用到一点数学知识，按照题目的定义丑数一定是丑数的2，3，或者5倍，所以可以看出最新的丑数和历史的丑数是有关系的，所以我们其实可以把历史的丑数都存起来，每次在求新的丑数的时候都求一遍历史丑数的2，3，5倍并且取这里面的最小值就是最新的丑数(前提是不能重复)。这里面又有一个问题，每次都求一遍历史的所有数据的2,3,5倍也很耗时，其实只要我们存起来的丑数是按照顺序存放的，那么可以把每次不超过最新丑数的最大元素的下标存起来，每次只要取这3个元素的最小值就可以了（因为由于顺序存放所以比最大元素小的那些元素的2，3，5倍的数据一定已经存在了）

public class ThirtyFour {public static void main(String[] args) {
//		System.out.println(uglyOne(1500));System.out.println(ugly(1500));}public static long ugly(int length) {int index = 1;long[] arr = new long[length];arr[0] = 1;int twoIndex = 0;int threeIndex = 0;int fiveIndex = 0;while(index < length) {long val = min(arr[twoIndex] * 2,arr[threeIndex] * 3,arr[fiveIndex] * 5);arr[index] = val;while(arr[twoIndex] * 2 <= arr[index]) {twoIndex++;}while(arr[threeIndex] * 3 <= arr[index]) {threeIndex++;}while(arr[fiveIndex] * 5 <= arr[index]) {fiveIndex++;}index = index + 1;}return arr[length - 1];}public static long min(long a,long b,long c) {if (a < b) {if (a < c) {return a;} else {return c;}} else {if (b < c) {return b;} else {return c;}}}public static long uglyOne(int length) {int data = 1;int count = 0;while(count < length) {int i = data;while(i % 2 == 0) {i /= 2;}while(i % 3 == 0) {i /= 3;}while(i % 5 == 0) {i /= 5;}if (i == 1) {count++;}data++;}return data - 1;}
}