使结果不超过阈值的最小除数
难度:
标签:
题目描述
代码结果
运行时间: 49 ms, 内存: 21.2 MB
解释
方法:
该题解采用了二分查找法来找到最小的除数。首先设定二分搜索的范围从1到数组nums的最大值。在每一步中，计算中间值mid作为试探的除数，然后使用这个除数对数组中的每个元素进行除法运算，并向上取整以保证结果是整数。然后将所有的结果求和，得到sump。如果sump大于阈值threshold，说明当前的除数太小，需要增大除数，因此将搜索范围的下限调整到mid+1；如果sump小于等于threshold，说明当前的除数可能合适或者还能更小，将搜索范围的上限调整到mid。最终，当左右界限相遇时，left或right就是所求的最小除数。
时间复杂度:
O(n log(max(nums)))
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在二分查找过程中，当求和结果sump大于阈值threshold时，需要将左界限left调整为mid+1而不是mid?
▷🦆
在计算sump时，使用向上取整的方法math.ceil(i / mid)，这种做法是否会在某些情况下导致结果不精确？
▷🦆
二分查找的初始右界限设置为数组nums的最大值，这种设置是否总是保证找到最小的除数，还是有可能错过更优的解？
▷