type
status
date
slug
summary
tags
category
icon
password
创建时间
Dec 18, 2024 03:29 AM
一个正整数如果能被
a 或 b 整除，那么它是神奇的。给定三个整数
n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。二分查找
题目是找到第
n 个数，转换题目，找到一个数 x，小于等于 x 的神奇数字有 n 个。以
n = 8，a = 4，b = 6 为例，a：4，8，12，16，20，24，28
b：6，12，18，24，30
4，6，8，12，16，18，20，24，28，30
第 8 个数是 24。但是我们反过来，找到一个数
x ，且小于等于 x 的神奇数字有 8 个。这样的数有 4 个，即 24，25，26，27。因此，我们需要找到满足条件最小的数。我可以使用利用二分法的性质，将判断条件设置为 check(x) >= n，最后找到的一定是最左边的数字。总结
二分法
特性：有单调性一定可以二分，没有单调性也可能可以二分。二分的本质是通过某一个性质可以将序列一分为二，保证在区间中是满足我们的性质的。也就是二分一定是“有解”的，满足我们定义的性质。是否符合题目的要求需要我们进一步去验证。
如何写二分？
- 先写
check函数，考虑一下check函数true和false如何更新；
- 如果是
l = mid，r = mid - 1，则mid = (l + r + 1)/2；如果是l = mid + 1，r = mid，则mid = (l + r)/2；
核心问题：每次更新区间，看是
r = mid 还是 l = mid。l = mid，则在写代码时 mid 是需要 +1的。求不满足性质序列的边界位置
模板
求满足性质序列的边界位置
模板
看
check 条件：nums[mid] >= target：最后找到的位置，一定是最左边，这样才满足条件，mid后面的所有元素都是大于等target；
nums[mid] <= target：最后找到的位置，一定是最右边，mid前面的所有元素都是小于等于target