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

📝 题目描述

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

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

​ 需要说明的是，数组中的每个数除以除数后都向上取整，比方说$7/3=3$、$10/2=5$、$1/2=1$。

​ 题目保证一定有解，即threshold >= nums.length。

📋 代码模板

java

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {

    }
}

typescript

function smallestDivisor(nums: number[], threshold: number): number {
    
}

💡 提示

1. $1\le nums.length\le 5\cdot {10}^4$
2. $1\le nums[i]\le {10}^6$
3. $nums.length\le threshold\le {10}^6$

🚀 示例

🖊️ 题解

​ 设正整数除数为 $div$ ，随着 $div$ 不断增大，数组中每个数 $nums[i]$ 除以 $div$ 的向上取整结果 $\left\lceil \frac{nums[i]}{divisor} \right\rceil $单调递减，它们的和 $total$ 同样也单调递减，其中 $total$ 的计算公式如下。

$$total=\sum _{i=0}^{n-1}\lceil \frac{nums[i]}{div}\rceil ,n=nums.length$$

​ 根据上述单调性，我们可以使用二分查找算法，找出满足条件 $total\le threshold$ 的最小除数 $answer$。因为只要得到 $answer$，以下两个条件都是必然成立的。

$$\sum _{i=0}^{n-1}\lceil \frac{nums[i]}{low}\rceil >threshold,low<answer$$$$\sum _{i=0}^{n-1}\lceil \frac{nums[i]}{high}\rceil \le threshold,high>answer$$

​ 二分查找的下限可以设置为 $1$，这是因为 $1$ 是最小正整数。而二分查找的上限可以设置为 $nums$ 数组中的最大值 $max$，这是因为题目保证有解，即 $threshold\ge n$，那么当除数 $div$ 为 $max$ 时，数组中每一项除以 $max$ 并向上取整后的结果都为 $1$，总和 $total$ 为 $n$，这确保我们不会遗漏最优解。

​ 综上所述，在区间 $[1,max]$ 中，使用二分查找，得到第一个使得条件 $total\le threshold$ 成立的元素，即为最小除数 $answer$​。其中，$total\le threshold$ 也是二分查找中 $check$ 函数为真的条件。

​ 为了进一步提高算法效率，我们还可以对 $check$ 函数进行优化，具体做法为：在统计总和 $total$ 时，若它的值已经超出了阈值 $threshold$，可直接中断统计，并返回 $false$。

java

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int low = 1, high = nums[0];
        for (int num : nums) {
            high = Math.max(num, high);
        }
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (check(nums, threshold, mid)) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    private boolean check(int[] nums, int threshold, int div) {
        int total = 0;
        for (int i = 0; i < nums.length && total <= threshold; i++) {
            total += (nums[i] + div - 1) / div;
        }
        return total <= threshold;
    }
}

typescript

function smallestDivisor(nums: number[], threshold: number): number {
    const check = (div: number): boolean => {
        let total = 0;
        for (let i = 0; i < nums.length && total <= threshold; i++) {
            total += Math.ceil(nums[i] / div);
        }
        return total <= threshold;
    }
    let low = 1, high = Math.max(...nums);
    while (low <= high) {
        const mid = low + Math.floor((high - low) / 2);
        if (check(mid)) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

💭 复杂度分析

​ 基于二分查找的解决方案的复杂度分析如下。

• 时间复杂度：$O(n\log M)$。其中 $M$ 为 数组中的最大值，$n$ 为数组长度。
• 空间复杂度：$O(1)$。