剑指 Offer 49 丑数

    
        标签：
        
            剑指 Offer
        
    发布于：2022-02-27 09:52:29
    编辑于：2022-04-01 16:20:08
    浏览量：878

概述

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];
    }
};

Links: sword-offer-49