剑指Offer面试题34题：丑数（Ugly Number）（while循环里面的三个小问题）

本文主要是介绍剑指Offer面试题34题：丑数（Ugly Number）（while循环里面的三个小问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

语言：C/C++语言

IDE: Mac/Xcode

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

分析：所谓一个数m是另一个数n的因子，是指n%m==0。根据丑数的定义，丑数能被2，3，5整除，也就是一个数能连续的被2整除，或者连续的被3整除，或者连续的被5整除，或者能被2，3，5的某种组合整除，例如（2*2*3*3*3*5）这种也可以。总结：包括2，3，5的因子，可能不包括2但包括3，肯能不包括3但包括5。就是不断的除2，3，5，如果最后的结果为1，那么则为丑数。

1.给某个数，判别这个数是否为丑数。

bool isUgly(int number)
{if(number<=0)return false;while(number%2==0)number/=2;while(number%3==0)number/=3;while(number%5==0)number/=5;return (number==1)?true:false;
}

2.暴力找第1500个丑数。

分析：找第1500个丑数作为函数的输入参数，那么从第一个丑数1开始找，不断递增，直到找到第1500个结束循环，循环条件为第1500个，最终输出返回这个第1500的丑数int。

则原型函数为： int GetUglyNumber(int index);

下面为剑指offer里面的实现。

int GetUglyNumber(int index)
{if(index<=0)return 0;int number=0,nth=0;while(nth<index){number++;if(isUgly(number))nth++;}return number;
}

但这里面有三个小问题：（这三个问题大家有想过吗？）

①.为什么 nth从0开始？？？

②.为什么number从0开始？？？

③.在while循环里面number++在 if判断前面？？？而不是下面这样？？？

（也就是number++在while中的位置）

while(nth<index) { if(isUgly(number))nth++;

   number++;

}

好，我慢慢解释。
答：在编程里面，数组的索引均是从0开始的，而不是从1开始的，所以大家都习惯以0开始。在这个题中第1500个丑数，则是nth=1499则终止循环。若是从1开始，则就是第1500个丑数。
nth=0;
while(nth<index).....
或者
nth=1;
while(nth<=index).....
这两个while的判断条件差了一个等号，这是第一个问题的答案。

其实第2问题和第3问题是一个问题。
那先假设程序如下：
nth=0,number=0；
while（nth<index）
{
if(isUgly(number))nth++
number++;
}
在第0次循环中，number为0不是丑数，nth为0，number自加变为1。
在第1次循环中，number为1是丑数，nth自加为1，number自加变为2。
在第2次循环中，number为2是丑数，nth自加为2，number自加变为3。
。。。。
在最后一次循环中(nth=1499)，number为xxx恰好是丑数，nth自加为1500，然后number自加1。
再次循环而nth不满足，则跳出循环，那么此时的number值是xxx+1 ，而不是xxx。所以关键在于最后这个number++；找到了第1500个丑数后，number再自加1，则跳出循环。这是最关键的！！！
又有人说：number从1开始行吗？
我的回答则是，那就是上面的分析中少了第0次循环而已，直接从第1次循环开始。最终还是会 number值为xxx+1 。
那么下面会对吗？？？？
number=1；
while（nth<index）
{
number++
if(isUgly(number))nth++
}
这样也是不对的，因为这是number从2开始判断的，则第一个丑数本身是1，而现在是2就错误了。
总结：
这是我的分析，看来控制number的起点和number++在if前后是有区别的，并不是随意放置，这是我们需要注意的重点，学习精髓，注重细节，否则得到的结果是不正确的。
而nth的起点与while里的判断条件相关。

此算法缺点是时间效率不高，太慢，一旦求第15000个丑数，估计得算半天。

3.明天待发