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 = [44,22,33,11,1], threshold = 5
输出：44

约束条件：

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

解题思路

这是一道典型的二分查找题目，关键是理解题意和确定搜索边界。

核心思路： 我们需要找到最小的除数，使得所有数字除以该除数后向上取整的和不超过阈值。由于除数越大，和越小，这具有单调性，因此可以使用二分查找。

解题步骤：

  1. 确定搜索边界：左边界为1（最小除数），右边界为数组最大值（当除数等于最大值时，和最小为数组长度）
  2. 二分查找：对于每个候选除数，计算所有数字除以它后向上取整的和
  3. 判断条件：如果和小于等于阈值，说明除数可能太大，尝试更小的；否则除数太小，需要增大

向上取整技巧： 对于正整数a和b，⌈a/b⌉ = (a + b - 1) / b，这样可以避免使用浮点运算。

时间复杂度优化：

  • 暴力枚举：O(max(nums) × n)
  • 二分查找：O(n × log(max(nums)))，显著提升效率

由于数据规模较大（nums长度可达5×10⁴，元素值可达10⁶），二分查找是必选的优化方案。

代码实现

class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        int left = 1, right = *max_element(nums.begin(), nums.end());
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int sum = 0;
            
            for (int num : nums) {
                sum += (num + mid - 1) / mid; // 向上取整
            }
            
            if (sum <= threshold) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
};

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        left, right = 1, max(nums)
        
        while left < right:
            mid = (left + right) // 2
            total = sum((num + mid - 1) // mid for num in nums)
            
            if total <= threshold:
                right = mid
            else:
                left = mid + 1
        
        return left

public class Solution {
    public int SmallestDivisor(int[] nums, int threshold) {
        int left = 1, right = nums.Max();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int sum = 0;
            
            foreach (int num in nums) {
                sum += (num + mid - 1) / mid; // 向上取整
            }
            
            if (sum <= threshold) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}

var smallestDivisor = function(nums, threshold) {
    let left = 1, right = Math.max(...nums);
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        let sum = 0;
        
        for (let num of nums) {
            sum += Math.floor((num + mid - 1) / mid); // 向上取整
        }
        
        if (sum <= threshold) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n × log(max(nums)))
空间复杂度O(1)

其中 n 是数组长度，max(nums) 是数组中的最大值。二分查找需要 log(max(nums)) 次迭代，每次迭代需要 O(n) 时间计算和值。

相关题目