LeetCode 1283 - Find the Smallest Divisor Given a Threshold (Medium)

Given an array of integers nums and an integer threshold, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.

Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).

It is guaranteed that there will be an answer.

Example 1:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2). 

Example 2:

Input: nums = [2,3,5,7,11], threshold = 11
Output: 3

Example 3:

Input: nums = [19], threshold = 5
Output: 4

Constraints:

• 1 <= nums.length <= 5 * 10^4
• 1 <= nums[i] <= 10^6
• nums.length <= threshold <= 10^6

方法：binary search

思路：整个nums可以形成的最大的sum，就是在当除数是1的时候。整个nums形成最小的sum，是当除数大于等于nums中最大的数的时候。所以如果要找到一个除数使得和可以小于等于threshold，那么我们需要做的其实就是在1和nums中最大的那个数之间找到一个合适的divisor。

time complexity：O(logn） space complexity：O(1)

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        l = 1 
        r = max(nums)
        
    
        divisor = float(‘inf‘) 
        while l <= r:
            mid = l + (r-l)//2
            tmp = self.getRes(nums, mid)
            if tmp <= threshold:
                divisor = min(divisor, mid)
                r = mid - 1 
            else:
                l = mid + 1 
        return divisor
                
    def getRes(self, nums, divisor):
        res = 0 
        
        for num in nums:
            res += math.ceil(num / divisor)
        
        return res 

LeetCode 1283 - Find the Smallest Divisor Given a Threshold (Medium)

原文：https://www.cnblogs.com/sky37/p/13939599.html