JZX轻语：简
LeetCode 1283 - 使结果不超过阈值的最小除数
发表于2024年07月16日
此类寻找满足某种条件中的最小值的题目，通常可以使用二分搜索来解决。对于本题，我们定义check函数为判断是否满足条件(即遍历数组，累加每个元素的除法取上界结果)的函数，然后使用二分搜索来寻找最小的满足check函数为True的值。
class Solution:
def smallestDivisor(self, nums: List[int], threshold: int) -> int:
def check(cand: int) -> bool:
return sum((num + cand - 1) // cand for num in nums) <= threshold
left, right = 1, max(nums)
while left <= right:
mid = (left + right) // 2
if check(mid):
right = mid - 1
else:
left = mid + 1
return left优化：在check函数内累加除法结果时，如果累加值已经超过了threshold，则可以直接返回False，这样可以减少一些不必要的计算。
class Solution:
def smallestDivisor(self, nums: List[int], threshold: int) -> int:
def check(cand: int) -> bool:
res = 0
for num in nums:
res += (num + cand - 1) // cand
if res > threshold:
break
return res <= threshold
left, right = 1, max(nums)
while left <= right:
mid = (left + right) // 2
if check(mid):
right = mid - 1
else:
left = mid + 1
return left