难度: Medium
给你一个整数数组 nums 和一个正整数 threshold ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。
请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。
每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。
题目保证一定有解。
示例 1：
输入：nums = [1,2,5,9], threshold = 6 输出：5 解释：如果除数为 1 ，我们可以得到和为 17 （1+2+5+9）。 如果除数为 4 ，我们可以得到和为 7 (1+1+2+3) 。如果除数为 5 ，和为 5 (1+1+1+2)。
示例 2：
输入：nums = [2,3,5,7,11], threshold = 11 输出：3
示例 3：
输入：nums = [19], threshold = 5 输出：4
提示：
1 <= nums.length <= 5 * 10^41 <= nums[i] <= 10^6nums.length <= threshold <= 10^6运行时间: 49 ms
内存: 21.2 MB
class Solution:
def smallestDivisor(self, nums: List[int], threshold: int) -> int:
import math
left,right=1,max(nums)
while left<right:
mid=(left+right)>>1
sump=sum([math.ceil(i/mid) for i in nums])
if sump>threshold:
left=mid+1
else:
right=mid
return left
该题解采用了二分查找法来找到最小的除数。首先设定二分搜索的范围从1到数组nums的最大值。在每一步中，计算中间值mid作为试探的除数，然后使用这个除数对数组中的每个元素进行除法运算，并向上取整以保证结果是整数。然后将所有的结果求和，得到sump。如果sump大于阈值threshold，说明当前的除数太小，需要增大除数，因此将搜索范围的下限调整到mid+1；如果sump小于等于threshold，说明当前的除数可能合适或者还能更小，将搜索范围的上限调整到mid。最终，当左右界限相遇时，left或right就是所求的最小除数。
时间复杂度: O(n log(max(nums)))
空间复杂度: O(1)
class Solution:
def smallestDivisor(self, nums: List[int], threshold: int) -> int:
import math
left, right = 1, max(nums) # 设置初始的搜索范围
while left < right: # 当左右界限未相遇时
mid = (left + right) >> 1 # 计算中间值
sump = sum([math.ceil(i / mid) for i in nums]) # 使用mid作为除数并向上取整求和
if sump > threshold: # 如果求和结果大于阈值
left = mid + 1 # 增大左界限，即增大除数
else: # 如果求和结果小于等于阈值
right = mid # 减小右界限，即考虑更小的除数
return left # 最终left和right相遇，返回结果
在二分查找中，当sump大于threshold，说明当前的除数mid太小，无法使得求和结果满足条件。如果继续使用mid作为左界限，那么在下一次循环中mid可能再次被计算，这会导致不必要的重复计算并且可能形成无限循环。因此，将左界限设为mid+1可以确保搜索空间向正确方向收缩，即不断尝试更大的除数，直到找到满足条件的最小除数。
使用math.ceil(i / mid)确保了每次除法结果都向上取整，这是题目要求的，以保证最终的求和结果不会低估。虽然这种方法可能会在某些情况下稍微增大求和结果，但它是符合题目要求的，并确保了不会因为取整误差导致求和结果小于实际应有的值，从而避免选择了一个实际上不满足条件的除数。因此，这种做法是精确的，符合题目的规定。
将初始右界限设置为数组nums的最大值是基于这样的考虑：如果除数等于数组中的最大值，则除法结果中最大的那个将是1（对最大值自身的除法结果），其他都是小于等于1的值，这是可能的最小的右界限设置。这样设置确保了覆盖所有可能的除数选项，不会错过更优的解。因此，这种设置是有效的，确保了能够找到最小的符合条件的除数。