LintCode-4.丑数 II

题目

描述

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

样例

如果n = 9, 返回 10

解答

思路

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

  1. 定义一个大小为n的数组u[n]用来存储有序丑数序列。
  2. 三个游标u2,u3,u5分别表示乘以2或3或5取得过最新丑数。
  3. 下一个丑数等于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;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LintCode-3.统计数字

    例如n=12,k=1,在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],我们发现1出现了5次 (1, 10, 11, 1...

    悠扬前奏
  • LintCode-373.奇偶分割数组

    悠扬前奏
  • LintCode-761. 最小子集

    给一非负整数数组. 取数组中的一部分元素, 使得它们的和大于数组中其余元素的和, 求出满足条件的元素数量最小值.

    悠扬前奏
  • C++面向对象作业1

    Angel_Kitty
  • 深入学习Apache Spark和TensorFlow

    想要了解更多关于Apache Spark的信息,请在2016年2月在纽约出席Spark东部峰会。

    林纾燊
  • Android项目实战(五十二):控制EditText输入内容大小写转换

    今日需求,EditText内容为一串字符串,要求将用户软键盘输入的小写字母在输入的时候自动转为大写字母,反之亦然。

    听着music睡
  • 深入学习Apache Spark和TensorFlow

    要了解更多关于Apache Spark的信息,请参考Spark Summit East in the New York in Feb 2016。

    用户1127524
  • 深入学习Apache Spark和TensorFlow

    神经网络在过去的几年中取得了惊人的进展,现在它们已经成为图像识别和自动翻译领域的领先技术。TensorFlow是Google发布的用于数值计算和神经网络的新框架...

    KX_WEN
  • leetcode 27 Remove Element

    @坤的
  • 每日算法系列【LeetCode 239】滑动窗口最大值

    给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

    godweiyang

扫码关注云+社区

领取腾讯云代金券