剑指 Offer 49 丑数

Tag: 剑指-Offer Posted on 2022-02-27 09:52:29 Edited on 2022-04-01 16:20:08 Views: 425

概述

https://leetcode-cn.com/problems/chou-shu-lcof/

https://leetcode.com/problems/ugly-number-ii/

暴力遍历法

遍历所有数字,直到找到第 n 个丑数。

时间复杂度 O(n^2)?因为 n^2 是第 n 个纯 2 质因子的数。

按个生成下一个丑数

丑数 = 2^a * 3^b * 5^c,其中 a,b,c 为自然数。

问题主要在于 a,b,c 之间的组合的结果的大小怎么比较?


我列了出来没发现规律,看了《剑指 Offer》 里给出的方法,就是直接用现有的丑数生成下一个丑数。

哎,我总想着有没有可以直接算出来的解法,却忘了我们的目的是 AC,不是 beat 100%!

实现的时候注意,内层三个更新 i2,i3 和 i5 的 while 循环条件中是 <=!因为我们要确保下一个丑数大于已有的丑数。

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> nums(n+1, 0);
        nums[1] = 1;
        int i2 = 1, i3 = 1, i5 = 1;
        int i = 2;
        while (i <= n) {
            nums[i] = min(nums[i2] * 2, min(nums[i3] * 3, nums[i5] * 5));
            while (nums[i2] * 2 <= nums[i]) i2 ++;
            while (nums[i3] * 3 <= nums[i]) i3 ++;
            while (nums[i5] * 5 <= nums[i]) i5 ++;
            i ++;
        }
        return nums[n];
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/