LintCode-4.丑数 II

悠扬前奏

发布于 2019-05-28 20:33:15

3200

发布于 2019-05-28 20:33:15

文章被收录于专栏：悠扬前奏的博客

题目

描述

设计一个算法，找出只含素因子2，3，5 的第 n 大的数。符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

样例

如果n = 9，返回 10

解答

思路

任何丑数都可以表示为：i^2 * j^3 * k^5；后一个丑数等于前面某个丑数乘以2或3或5：

定义一个大小为n的数组u[n]用来存储有序丑数序列。
三个游标u2,u3,u5分别表示乘以2或3或5取得过最新丑数。
下一个丑数等于min(u[u2]*2, u[u3]*3, u[u5]*5)，并根据因子对u2或u3或u5递增。

代码

class Solution {
    /**
     * @param n an integer
     * @return the nth prime number as description.
     */
    public int nthUglyNumber(int n) {
        // Write your code here
        int[] u = new int[n];
        u[0] = 1;
        int u2 = 0,u3 = 0, u5 = 0;
        for(int i = 1; i < n; i++){
            u[i] = min(min(u[u2]*2,u[u3]*3),u[u5]*5);
            if((u[i]/u[u2]) == 2) u2++;
            if((u[i]/u[u3]) == 3) u3++;
            if((u[i]/u[u5]) == 5) u5++;
        }
        return u[n-1];
    }
    public int min(int a, int b){
        return a < b ? a : b;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017.06.28 ，如有侵权请联系 cloudcommunity@tencent.com 删除

min