【二分查找】1201. 丑数 III
前言
二分查找是一种高效的查找算法，其时间复杂度为 O(log n)。在许多情况下，我们需要在一个有序数组中找到某个目标值的搜索范围。本文将介绍一种基于二分查找的搜索范围查找算法，该算法能够快速找到目标值在数组中的起始和结束位置。
在另一篇博客里讲过二分法的模板：
《二分法的模板讲解》
🕺作者： 迷茫的启明星
学习路线
C语言从0到1
C++初阶
数据结构从0到1
😘欢迎关注：👍点赞🙌收藏✍️留言
🏇码字不易，你的👍点赞🙌收藏❤️关注对我真的很重要，有问题可在评论区提出，感谢阅读！！！
问题背景
给定四个整数：n、a、b、c，我们需要设计一个算法来找出第n个丑数。丑数是指可以被a、b或c整除的正整数。
原题链接
https://leetcode.cn/problems/ugly-number-iii/description/
问题分析
为了解决这个问题，我们可以利用容斥原理来计算区间 [1, mid] 内的丑数个数。容斥原理是组合数学中的一个核心概念，用于计算多个集合的并集的元素数量。在本问题中，我们需要计算被 a、b、c 整除的正整数数量，以及被 ab、ac、bc 整除的正整数数量。然后，从总个数中减去被 ab、ac、bc 整除的正整数数量，最后再加上被 abc 整除的正整数数量。
算法实现
首先，我们需要计算a、b、c的最小公倍数abc，以及ab、ac、bc的最小公倍数。
初始化结果范围为[min({a, b, c}), 2 * 10^9]。
使用二分查找法，在[l, r]范围内查找第n个丑数。
在每次迭代中，计算中间值mid，并使用容斥原理计算[1, mid]中的丑数个数。
根据丑数个数与n的大小关系，更新搜索范围。
当搜索范围收缩到l+1 == r时，返回r作为第n个丑数。
代码
class Solution { public: typedef long long ll; // greatest common divisor 最大公约数 ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } // least common multiple 最小公倍数 ll lcm(ll a, ll b) { return a * b / gcd(a, b); } int nthUglyNumber(int n, int a, int b, int c) { ll ab = lcm(a, b), ac = lcm(a, c), bc = lcm(b, c); ll abc = lcm(ab, c); //本题结果在 [1, 2 * 10^9] 的范围内，优化为 [min({a,b,c}), 2 * 10^9] ll l = min({a,b,c})-1, r = 2e9+1; while (l+1 != r) { ll mid = (l+r)>>1; // 容斥原理：计算 cnt 为[1,mid]中的丑数个数 ll cnt = mid / a + mid / b + mid / c - mid / ab - mid / ac - mid / bc + mid / abc; if (cnt < n) { l = mid; } else { r = mid; } } return (int)r; } };
总结
本文介绍了一种高效的算法来解决求解第n个丑数的问题。通过使用容斥原理和二分查找法，我们可以在较短的时间内找到第n个丑数。在实际应用中，这种算法可以应用于各种需要求解丑数的场景，提高计算效率。
本文由mdnice多平台发布
