#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <unordered_map>
using namespace std;
/*解题思路：
* http://blog.csdn.net/coder_xia/article/details/6707600 */
int Min(int a, int b, int c)
{
int temp = (a < b ? a : b);
return (temp < c ? temp : c);
}
int FindUgly(int n) //
{
int* ugly = new int[n];
ugly[0] = 1;
int index2 = 0;
int index3 = 0;
int index5 = 0;
int index = 1;
while (index < n)
{
int val = Min(ugly[index2]*2, ugly[index3]*3, ugly[index5]*5); //竞争产生下一个丑数
if (val == ugly[index2]*2) //将产生这个丑数的index*向后挪一位；
++index2;
if (val == ugly[index3]*3) //这里不能用elseif，因为可能有两个最小值，这时都要挪动；
++index3;
if (val == ugly[index5]*5)
++index5;
ugly[index++] = val;
}
int result = ugly[n-1];
delete[] ugly;
return result;
}
int main()
{
int num;
cin >> num;
cout << FindUgly(num) << endl;
return 0;
}
面试题之丑数的C++实现求解（孤陋寡闻了，才知道丑数这么high的东东）
