谷歌面试题解析：寻找丑数

谷歌面试题解析：寻找丑数2014-12-24题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。

分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。

这段题刚开始的想法是从1开始递增遍历，找出1500个是丑数的数，并打印出来。

实现如下：

#include<stdio.h>#include<string.h>#include<iostream>#include<stdlib.h>using namespace std;bool isUgly（int d）{while（d%2 == 0）d/=2;while（d%3 == 0）d/=3;while（d%5 == 0）d/=5;if（d == 1）return true;return false;}void printUglyN（int num）{int k = 0;for（int i= 1; k < num; i ++）{if（isUgly（i））{k++;cout << i << "	";}}}int main（）{printUglyN（1500）;return 0;}

上面计算次数很多，可以采用一种简单的方法，思想很精妙。

后面的数是前面数的基础上＊2或3或5得到的。可以用三个指针指向乘以2，乘以3，乘以5后位置。

请看算法实现：

#include<stdio.h>#include<string.h>#include<iostream>#include<stdlib.h>//#define min（a, b, c） （（（（a）>（b））？（b）:（a）） > （c）） ？ c : （（（a）>（b））？（b）:（a））using namespace std;int min（int a, int b, int c）{int t = a > b ？ b : a;return t> c ？ c:t;}void findUglyN（int *uglys, int num）{uglys[0] = 1;int p2 = 0;int p3 = 0;int p5 = 0;int i = 1;while（ i < num）{uglys[i] = min（uglys[p2]*2, uglys[p3]*3, uglys[p5]*5）;if（uglys[i] == uglys[p2]*2） p2++;if（uglys[i] == uglys[p3]*3） p3++;if（uglys[i] == uglys[p5]*5） p5++;i++;}}int main（）{int num = 1500;int *uglys = new int[num];findUglyN（uglys, num）;for（int i = 0; i < num; i++）cout << uglys[i] << "	";delete[] uglys;return 0;}

作者：csdn博客 hhh3h