滴滴出行2018校园招聘网申笔试-研发工程师-编程题二

题目

描述

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

输入

N

输出

第 N 个丑数

Example

Input

7

Output

8

题解

思路

• 剑指offer 原题
• 定义 m2,m3,m5,c,now 分别为 2 的倍数,3 的倍数,5 的倍数,已找到的丑数个数,当前的丑数,
• 第 i 个丑数取 m2,m3,m5 三者中的最小值,然后更新 m2,m3,m5,c
• 时间复杂度 O(n)

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n,m2,m3,m5,c,now;
    cin>>n;
    now=c=1;
    m2=2,m3=3,m5=5;
    while(c<n)
    {
        now=min(m2,min(m3,m5));
        if(m2==now) m2+=2;
        if(m3==now) m3+=3;
        if(m5==now) m5+=5;
    }
    cout<<now;
}