[LeetCode] 1283. Find the Smallest Divisor Given a Threshold

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

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

The test cases are generated so 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 of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).

Example 2:
Input: nums = [44,22,33,11,1], threshold = 5
Output: 44

Constraints:
1 <= nums.length <= 5 * 104
1 <= nums[i] <= 106
nums.length <= threshold <= 106

使结果不超过阈值的最小除数。

给你一个整数数组 nums 和一个正整数 threshold ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。

请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。

每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。

题目保证一定有解。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-smallest-divisor-given-a-threshold
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是二分法。按照题意规定的计算方式，我们要找到一个合适的除数。但是如何确定除数的范围呢，下限肯定是1，上限应该是数组中最大的数字，我们暂且定义他为 max。因为如果除 max 都大了，做如上那一通操作得出的除法结果求和只会是离 threshold 越来越远。

确定好了除数的上限和下限之后，我们就可以开始做二分了。这里做二分没什么可说的，我们写一个 helper 函数，按照题意，每次找到一个 mid，去计算那个所谓的 sum 是否是一个最大的且小于 threshold 的结果。

复杂度

时间O(nlogn)
空间O(1)

代码

Java实现

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int left = 1;
        int right = 1;
        for (int num : nums) {
            right = Math.max(right, num);
        }
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (helper(nums, mid) > threshold) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private int helper(int[] nums, int divisor) {
		int sum = 0;
		for (int num : nums) {
			sum += num / divisor;
			// 不能整除的时候，需要向上取整
			if (num % divisor != 0) {
				sum++;
			}
		}
		return sum;
	}
}