LeetCode_容斥原理_二分搜索_中等_1201.丑数 III

迷南。 2023-10-08 18:52 0阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。

丑数是可以被 a 或 b 或 c 整除的正整数。

**示例 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。

**示例 4：**  
输入：n = 1000000000, a = 2, b = 217983653, c = 336916467  
输出：1999999984

**提示：**  
1 <= n, a, b, c <= 109  
1 <= a \* b \* c <= 1018  
本题结果在 \[1, 2 \* 109\] 的范围内

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/ugly-number-iii

## 2.思路 ##

（1）容斥原理 & 二分搜索  
思路参考[该 LeetCode 用户题解][LeetCode]。

① 前置知识：  
1）\[1, i\] 中能够被 a 整除的数个数为 i / a。  
2）容斥原理：∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A ∩ B∣−∣A ∩ C∣−∣B ∩ C∣+∣A ∩ B ∩ C∣。

② 那么 \[1, i\] 中能够被 a 或 b 或 c 整除的数个数是否 = i / a + i / b + i / c = i / a + i / b + i / c？显然不等于，因为其中有些数即能被 a，b 和 c 整除。因此，我们要考虑如何去除重复计算的数。利用容斥原理，\[1, i\] 中能被 a 或 b 或 c 整除的数的个数 cnt = i / a - i / b - i / c - i / ab - i / bc - i / ac + i / abc = i / a−i / b−i / c − i / ab − i / bc − i / ac + i / abc。其中 i / ab 代表能被 a 和 b 整除的数，其他同理。

③ 题目需要返回第 n 个丑数，由于 n 很大，直接暴力求解显然不行。但是其实明白了上面的信息后，很容易就可以想到二分法来求解答案。可以将题目转化为：在 \[1, i\] 中求解能被 a 或 b 或 c 整除的数个数之和大于等于 n 的最小的 i 即是我们的答案。同时这也是正是二分搜索中**搜索最左侧边界**的情况。

④ 显然对于答案 x 来说，\[1, x − 1\] 必然是不满足要求，而 \[x, INF\] 都能够满足要求。此外，根据[【算法】二分搜索][Link 1]这篇文章中的应用技巧，我们可以抽象出 x、f(x) 和 target：

<table> 
 <thead> 
  <tr> 
   <th>x</th> 
   <th>大于等于 1 的整数，其范围为 [1, Integer.MAX_VALUE]</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>f(x)</td> 
   <td>f(x) = getCnt(int x, int a, int b, int c)，其中 getCnt 返回的是 [1, x] 中能被 a 或 b 或 c 整除的数的个数，所以 f(x) 在 x 的定义域上是非严格单调递增的</td> 
  </tr> 
  <tr> 
   <td>target</td> 
   <td>题目中给的 n</td> 
  </tr> 
 </tbody> 
</table>

> 有关**最大公因数和最小公倍数**的具体细节可以查看[【数论算法】最大公约数 & 最小公倍数][Link 2]。

相关题目：  
[LeetCode\_因式分解\_简单\_263.丑数][LeetCode_263.]  
[LeetCode\_动态规划\_中等\_264.丑数 II][LeetCode_264._ II]  
[LeetCode\_动态规划\_中等\_313.超级丑数][LeetCode_313.]  
[LeetCode\_二分搜索\_容斥原理\_困难\_878.第 N 个神奇数字][LeetCode_878._ N]

## 3.代码实现（Java） ##

//思路1————容斥原理 & 二分搜索
    class Solution {
        
        public int nthUglyNumber(int n, int a, int b, int c) {
        
            int left = 1;
            int right = Integer.MAX_VALUE;
            while (left <= right) {
        
                int mid = left + (right - left) / 2;
                if (getCnt(mid, a, b, c) < n) {
        
                    left  = mid + 1;
                } else {
        
                    right = mid - 1;
                }
            }
            return left;
        }
    
        //返回 [1, mid] 中能被 a 或 b 或 c 整除的数的个数
        public long getCnt(int mid, int a, int b, int c) {
        
            long ab = lcm(a, b), ac = lcm(a, c), bc = lcm(b, c), abc = lcm(lcm(a, b), c);
            long cnt = (long)mid / a + mid / b + mid / c - mid / ac - mid / bc - mid /ab + mid / abc;
            return cnt;
        }
    
        public long gcd(long a, long b) {
        
            return b == 0 ? a : gcd(b, a % b);
        }
    
        public long lcm(long a, long b) {
        
            return a / gcd(a, b) * b;
        }
    }

[LeetCode]: https://leetcode.cn/problems/ugly-number-iii/solution/javac-rong-chi-yuan-li-er-fen-cha-zhao-b-bf69/
[Link 1]: https://blog.csdn.net/weixin_43004044/article/details/128591151
[Link 2]: https://blog.csdn.net/weixin_43004044/article/details/128888636
[LeetCode_263.]: https://blog.csdn.net/weixin_43004044/article/details/125957089
[LeetCode_264._ II]: https://blog.csdn.net/weixin_43004044/article/details/125969827
[LeetCode_313.]: https://blog.csdn.net/weixin_43004044/article/details/126074560
[LeetCode_878._ N]: https://blog.csdn.net/weixin_43004044/article/details/127976245