1283. 使结果不超过阈值的最小除数 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

解题思路

输入： 一个整数数组 nums 和一个正整数 threshold

输出： 找出一个最小的除数使得数组里每个数除了以后相加小于等于 threshold

本题属于二分答案类问题。

这道题和 875 题类似，都是找到一个 最大/最小 值满足 小于等于某个值 。

因此我们要从 [1, max(nums)] 中找到答案

每次都通过二分查找中间值，并且判断是否满足条件，满足条件就记录下来继续去找

由于是找最小值所以往左侧区间找，直到 right < left 终止，最终返回最后一次记录的答案

代码实现

python

from typing import List
from math import ceil

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        # 不需要排序，因为只与数值的大小和总和有关，与顺序无关
        left, right = 1, max(nums)
        ans = right  # 初始化答案为最大可能的除数

        while left <= right:
            mid = (left + right) // 2  # 当前尝试的除数
            total = 0
            
            for num in nums:
                total += ceil(num / mid)  # 计算所有数字除以当前除数后向上取整的和

            if total <= threshold:
                # 如果总和小于等于阈值，说明可以尝试更小的除数
                ans = mid
                right = mid - 1
            else:
                # 总和超过阈值，说明除数太小，需要更大的除数
                left = mid + 1

        return ans  # 返回满足条件的最小除数

javascript

/**
 * @param {number[]} nums
 * @param {number} threshold
 * @return {number}
 */
var smallestDivisor = function(nums, threshold) {
    let left = 1;
    let right = Math.max(...nums);
    let ans = right;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        let total = 0;

        for (let num of nums) {
            total += Math.ceil(num / mid);
        }

        if (total <= threshold) {
            ans = mid
            right = mid - 1
        } else {
            left = mid + 1;
        }
    }

    return ans;
};

复杂度分析

时间复杂度：O(nlog m)

空间复杂度：O(1)

链接

1283 国际版

1283 中文版