Medium

题目描述

丑数是一个正整数，能被 a、b 或 c 中的任意一个数整除。

给定四个整数 n、a、b 和 c，返回第 n 个丑数。

示例 1：

输入：n = 3, a = 2, b = 3, c = 5
输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 第 3 个是 4。

示例 2：

输入：n = 4, a = 2, b = 3, c = 4
输出：6
解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 第 4 个是 6。

示例 3：

输入：n = 5, a = 2, b = 11, c = 13
输出：10
解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 第 5 个是 10。

提示：

  • 1 <= n, a, b, c <= 10^9
  • 1 <= a * b * c <= 10^18
  • 保证结果在范围 [1, 2 * 10^9] 内。

解题思路

这是一个典型的二分查找 + 容斥原理的问题。

核心思路： 我们不需要逐一生成丑数，而是使用二分查找来找到第 n 个丑数。关键在于构造一个函数 f(k)，它能计算小于等于 k 的丑数个数。

计算小于等于 k 的丑数个数： 使用容斥原理：

  • 能被 a 整除的数有 k/a 个
  • 能被 b 整除的数有 k/b 个
  • 能被 c 整除的数有 k/c 个
  • 但要减去重复计算的：能被 lcm(a,b)、lcm(b,c)、lcm(a,c) 整除的数
  • 再加上被三重计算减掉的：能被 lcm(a,b,c) 整除的数

公式：f(k) = k/a + k/b + k/c - k/lcm(a,b) - k/lcm(b,c) - k/lcm(a,c) + k/lcm(a,b,c)

二分查找： 在范围 [1, 2*10^9] 中二分查找，找到最小的 k 使得 f(k) >= n。

辅助函数： 需要实现 gcd（最大公约数）和 lcm（最小公倍数）函数。

代码实现

class Solution {
private:
    long long gcd(long long a, long long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    long long lcm(long long a, long long b) {
        return a / gcd(a, b) * b;
    }
    
    long long count(long long k, int a, int b, int c) {
        long long ab = lcm(a, b);
        long long ac = lcm(a, c);
        long long bc = lcm(b, c);
        long long abc = lcm(ab, c);
        
        return k/a + k/b + k/c - k/ab - k/ac - k/bc + k/abc;
    }
    
public:
    int nthUglyNumber(int n, int a, int b, int c) {
        long long left = 1, right = 2000000000LL;
        
        while (left < right) {
            long long mid = left + (right - left) / 2;
            if (count(mid, a, b, c) < n) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return (int)left;
    }
};

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        def gcd(x, y):
            while y:
                x, y = y, x % y
            return x
        
        def lcm(x, y):
            return x // gcd(x, y) * y
        
        def count(k):
            ab = lcm(a, b)
            ac = lcm(a, c)
            bc = lcm(b, c)
            abc = lcm(ab, c)
            
            return k//a + k//b + k//c - k//ab - k//ac - k//bc + k//abc
        
        left, right = 1, 2000000000
        
        while left < right:
            mid = (left + right) // 2
            if count(mid) < n:
                left = mid + 1
            else:
                right = mid
        
        return left

public class Solution {
    private long Gcd(long a, long b) {
        return b == 0 ? a : Gcd(b, a % b);
    }
    
    private long Lcm(long a, long b) {
        return a / Gcd(a, b) * b;
    }
    
    private long Count(long k, int a, int b, int c) {
        long ab = Lcm(a, b);
        long ac = Lcm(a, c);
        long bc = Lcm(b, c);
        long abc = Lcm(ab, c);
        
        return k/a + k/b + k/c - k/ab - k/ac - k/bc + k/abc;
    }
    
    public int NthUglyNumber(int n, int a, int b, int c) {
        long left = 1, right = 2000000000L;
        
        while (left < right) {
            long mid = left + (right - left) / 2;
            if (Count(mid, a, b, c) < n) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return (int)left;
    }
}

var nthUglyNumber = function(n, a, b, c) {
    function gcd(x, y) {
        while (y !== 0) {
            [x, y] = [y, x % y];
        }
        return x;
    }
    
    function lcm(x, y) {
        return Math.floor(x / gcd(x, y)) * y;
    }
    
    function count(k) {
        const ab = lcm(a, b);
        const ac = lcm(a, c);
        const bc = lcm(b, c);
        const abc = lcm(ab, c);
        
        return Math.floor(k/a) + Math.floor(k/b) + Math.floor(k/c) 
             - Math.floor(k/ab) - Math.floor(k/ac) - Math.floor(k/bc) 
             + Math.floor(k/abc);
    }
    
    let left = 1, right = 2000000000;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (count(mid) < n) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(log(2×10^9) × log(max(a,b,c))) ≈ O(32 × 30) = O(1)
空间复杂度O(1)

时间复杂度分析：二分查找进行 O(log(2×10^9)) 次，每次计算 count 函数需要 O(log(max(a,b,c))) 时间来计算 GCD，总体是常数级别。空间复杂度为常数。

相关题目