丑数问题

问题描述

由2,3,5组成的数,即数由2,3,5因数组成,不含有其他因数.其中1是特殊的丑数.求第n个丑数.

[1,2,3,4,5,6,8,9,10,12,...].

分析

由于只由2,3,5三个因数组成,则可以对数进行因数分解,若只由2,3,5因数组成,则为丑数.从1开始进行循环寻找:

int uglyNum(int n) {
	int number = 1;					//从1开始
	int count = 0;						//计数
	while (1) {							//循环查找
		int num = number;			//用于因数分解
		while (num % 2 == 0) {	//是否可以被2因数分解
			num /= 2;
		}
		while (num % 3 == 0) {	//是否可以被3因数分解
			num /= 3;
		}
		while (num % 5 == 0) {	//是否可以被5因数分解
			num /= 5;
		}

		if (num == 1) {					//是否只能被2,3,5因数分解
			count++;						//是则计数加一
		}

		if (count == n) {				//第n个则跳出循环
			break;
		} else {
			number++;					//不是则继续循环
		}
	}

	return number;
}

这样的做法当n很大时,都要从1一直循环n次,很耗时,而且当中还有很多因数分解的过程.

再次分析

再次分析发现数组[1,2,3,4,5,6,8,9,10,12,...]
除了第一个丑数1,向后的丑数,都是由之前丑数x2,3,5得到的,并且丑数是一个递增的过程.
即2=1x2,3=1x3,4=2x2,5=1x5,6=2x3
所以完全可以让之前的丑数x2,3,5,比较数值获取下一个丑数.

#define MAX 99999					//数组最大值
int uglyNum(int n) {
	int uglys[MAX] = {1};				//保存丑数数组
	int count = 1;							//因有一个数,所以从1开始
	//1的情况另做判断
	if (n == 1) {
		return 1;
	}
	while (1) {
		int chooseTwo = 0;				//记录和2相乘的数据
		int chooseThree = 0;			//记录和3相乘的数据
		int chooseFive = 0;				//记录和5相乘的数据
		for (int i = 0; i < count; i++) {					//循环前面丑数和2相乘
			if (uglys[i] * 2 > uglys[count - 1]) {		//找到第一个大于前一个的丑数,直接记录然后break
				chooseTwo = uglys[i] * 2;
				break;
			}
		}
		for (int i = 0; i < count; i++) {					//和2同理
			if (uglys[i] * 3 > uglys[count - 1]) {
				chooseThree = uglys[i] * 3;
				break;
			}
		}
		for (int i = 0; i < count; i++) {					//和2同理
			if (uglys[i] * 5 > uglys[count - 1]) {
				chooseFive = uglys[i] * 5;
				break;
			}
		}
		//比较三个数的大小,小的即为丑数,加入数组中
		int temp = chooseTwo <= chooseThree ? chooseTwo : chooseThree;
		uglys[count] = temp <= chooseFive ? temp : chooseFive;
		//计数器加一
		count++;
		//如果是第n个就直接返回
		if (count == n) {
			//数组最后一个元素下标是count-1
			return uglys[count - 1];
		}
	}
}

执行速度显著提高,空间换取时间的做法.