leetcode
leetcode 2651 ~ 2700
丑数 III

丑数 III

难度:

标签:

题目描述

An ugly number is a positive integer that is divisible by a, b, or c.

Given four integers n, a, b, and c, return the nth ugly number.

 

Example 1:

Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.

Example 2:

Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.

Example 3:

Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.

 

Constraints:

  • 1 <= n, a, b, c <= 109
  • 1 <= a * b * c <= 1018
  • It is guaranteed that the result will be in range [1, 2 * 109].

代码结果

运行时间: 22 ms, 内存: 16.1 MB

解释

方法:

该题解使用了最小公倍数（Least Common Multiple, LCM）和二分查找的策略。首先，计算a, b, c两两之间以及三者的最小公倍数（ab, ac, bc, abc）。定义一个函数f(k)来计算小于或等于k的丑数数量，这是通过包含-排除原理计算得出的：单独计算k能被a, b, c整除的数的数量，减去k能被ab, ac, bc整除的数的数量。通过这个函数，可以快速计算出任意数k下的丑数数量。接着，使用二分查找方法在有效范围内搜索第n个丑数。首先通过abc整除周期估计位置，然后在周期内精确搜索。

时间复杂度:

O(log(abc))

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在计算小于或等于k的丑数数量时，需要单独计算k能被a, b, c整除的数的数量，然后再减去k能被ab, ac, bc整除的数的数量？
▷
这种方法基于组合数学中的包含-排除原理。首先单独计算k能被a, b, c整除的数的数量，是为了确定所有可能由a, b, c生成的丑数。然而，这样单独计算会导致那些同时能被两个或三个数整除的数被重复计算多次。例如，一个数如果同时能被a和b整除，那么它在计算能被a整除的数和能被b整除的数时会被计算两次。因此，我们需要减去这些重复计算的部分，即减去k能被ab, ac, bc整除的数的数量。最后，如果一个数能同时被a, b, c三个数整除，我们在前面的步骤中减少了过多（实际上减了三次），因此还需要再加回来，这就是为什么还要考虑三个数的最小公倍数abc的原因。
🦆
如何确保二分查找在寻找第n个丑数时的正确性，特别是在处理边界条件如周期末尾或开始时？
▷
为了确保二分查找的正确性，首先估计一个周期（由最小公倍数abc定义），在这个周期内，丑数的数量是固定的。通过计算整个周期内的丑数数量，可以快速定位到第n个丑数可能所在的大致范围。如果通过这个周期的计算，第n个丑数落在某个周期的边界上，可以直接返回周期的整数倍。如果不在边界上，那么就在该周期内使用二分查找。二分查找的过程中，通过不断调整搜索的上下界，直到找到确切的第n个丑数。这一过程中，必须仔细处理每次的上下界调整，确保不会错过任何可能的丑数，并且在达到终止条件时能正确停止。
🦆
在实现二分查找的时候，你是如何选择二分查找的起始和结束点的，为什么选择这个范围？
▷
二分查找的起始点和结束点的选择基于对问题的理解和周期性特征的利用。起始点通常设置为周期的开始，即0或者周期的最小值，而结束点则设置为一个周期的长度，即最小公倍数abc。选择这个范围的原因是，通过前面的计算和理论分析，我们知道一个周期内会包含所有可能的丑数类型，且数量固定。因此，一个周期的范围足以覆盖所有需要考察的情况，以确定具体的第n个丑数在哪里。通过设置这样的范围，我们可以有效地利用二分查找，减少不必要的计算，同时确保搜索的准确性。

相关问题

最接近的因数给植物浇水