面试题49:丑数

题目

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

解题思路

• 丑数的详细定义:
  丑数只能被2、3和5整除，也就是说，如果一个数能被2整除，就连续除以2；如果能被3整除，就连续除以3；如果能被5整除，就连续除以5.如果最后得到的是1，则这个数就是丑数；否则不是。
• 创建数组保存已经找到的丑数，用空间换时间

1. 创建一个数组，里面的数字是排好序的丑数，每个丑数是前面丑数乘以2、3或者5得到的。
2. 如何确保数组中的丑数是排好序的?
   每次的丑数都应该是M1(丑数乘以2)，M2(丑数乘以3)，M3(丑数乘以5)中的最小者

代码

1. 开辟数组pUglyNumbers存放排好序的丑数
2. 定义三个指针变量*pMultiply2、*pMultiply3、*pMultiply5来表示2、3和5的倍数
3. *pMultiply2、*pMultiply3、*pMultiply5依次取排好序的丑数中的值。也就是代码中++pMultiply2指的是指针指向排好序的数组pUglyNumbers中的下一个元素。

class Solution{
    public:
        
        int Min(int number1,int number2,int number3)
        {
            int min = (number1 < number2)?number1:number2;
            min = (min<number3)?min:number3;
            return min;
        }
        int GetUglyNumber(int index)
        {
            if(index <= 0)
            {
                return 0;
            }

            int *pUglyNumbers = new int[index];
            pUglyNumbers[0] = 1;
            int nextUglyIndex = 1;

            int *pMultiply2 = pUglyNumbers;
            int *pMultiply3 = pUglyNumbers;
            int *pMultiply5 = pUglyNumbers;

            while(nextUglyIndex < index)
            {
                int min = Min(*pMultiply2*2,*pMultiply3*3,*pMultiply5*5);
                pUglyNumbers[nextUglyIndex] = min;
                cout << "pUglyNumbers[" << nextUglyIndex << "] =" << min;
                cout << " " <<*pMultiply2 << *pMultiply3 << *pMultiply5 << endl;
                while(*pMultiply2*2 <= pUglyNumbers[nextUglyIndex])
                {
                    ++pMultiply2;
                    if(*pMultiply2 == 7)
                    {
                        cout << "输出7" <<endl;
                    }
                }

                while(*pMultiply3*3 <= pUglyNumbers[nextUglyIndex])
                {
                    ++pMultiply3;
                }

                while(*pMultiply5*5 <= pUglyNumbers[nextUglyIndex])
                {
                    ++pMultiply5;
                }
                ++nextUglyIndex;
            }
            int ugly = pUglyNumbers[nextUglyIndex-1];
            delete[] pUglyNumbers;
            return ugly;
        }
};

完整代码见Github