264. Ugly Number II丑数

2024-01-04 19:38

文章标签 ii number 丑数 ugly 264

本文主要是介绍264. Ugly Number II丑数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

解答

逐个判断每个整数是不是丑数，效率低

public:bool isUglyNumber(int num){while(num%2 == 0)num/=2;while(num%3 ==0)num/=3;while(num%5 == 0)num/=5;if(num == 1)return true;elsereturn false;}int GetUglyNumber_Solution(int index) {if(index <=0)return 0;int count = 0;int i = 0;while(count<index){   ++i;if(isUglyNumber(i))++count;}return i;}

空间换时间，创建数组保存已经找到的丑数

　　根据丑数的定义可以知道，丑数应该是另一个丑数乘以2或3或5的结果（1除外）。因此我们可以创建一个数组，里面的数字是排序好的丑数。
　　这种思路的关键在于怎样确保数组里面的丑数是排序好的。假设数组中已经有了若干个排序好的丑数。我们将目前最大的丑数记为M。
　　那么下一个丑数肯定是前面某一个丑数乘以2或3或5的结果。所以我们首先考虑把已有的每个丑数乘以2。在乘以2的时候，能得到若干个小于或等于M的数。由于是按照顺序生成的，小于或等于M的数肯定已经在数组中了，不需要考虑这些数；此外还会得到若干个大于M的结果，但我们只需要第一个大于M的结果。我们把乘以2大于M的第一个数记为M2。同样，我们可以得到M3和M5。那么下一个丑数就应该是M2，M3,M5中的最小值。
　　上述分析中要把M之前的每个丑数都乘以2、3和5。但实际不需要这么做。以乘以2为例，肯定存在一个丑数T2，排在它之前的每一个丑数乘以2得到的结果都小于M，在它之后的每一个丑数乘以2都大于M。我们只需记下这个数的位置，同时每次生成新的丑数时，去更新这个T2即可。同理，对3和5来说，存在T3和T5。

int GetUglyNumber_Solution(int index){if(index <= 0)return 0;int* uglyNumbers = new int[index];uglyNumbers[0] = 1;int nextUglyNumber = 1;int* pMultiple2 = uglyNumbers;int* pMultiple3 = uglyNumbers;int* pMultiple5 = uglyNumbers;while(nextUglyNumber < index){uglyNumbers[nextUglyNumber] = min(*pMultiple2*2,min(*pMultiple3*3,*pMultiple5*5));while(*pMultiple2*2<=uglyNumbers[nextUglyNumber])++pMultiple2;while(*pMultiple3*3<=uglyNumbers[nextUglyNumber])++pMultiple3;while(*pMultiple5*5<=uglyNumbers[nextUglyNumber])++pMultiple5;++nextUglyNumber;}int ret = uglyNumbers[nextUglyNumber-1];delete [] uglyNumbers;return ret;}