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

题目描述#

给定一个整数数组 nums 和一个正整数 threshold，需要选择一个正整数作为除数 d。将数组中的每个元素都除以 d 并向上取整，再把这些结果求和。请你找到所有能让最终和不超过 threshold 的除数中，最小的那个。

题目保证一定存在合法解。

思路#

这是一道二分答案

“花费一个 log 的时间，增加了一个条件。” —— 二分答案

二分查找除数#

除数的下界是 1，上界可以设置为 nums 中的最大值；只要除数超过最大值，所有元素都会被向上取整到 1。
使用二分查找定位满足条件的最小除数：对于一个候选除数 mid，如果经过向上取整的总和不超过 threshold，说明可以尝试更小的除数；否则需要增大除数。

检查函数#

遍历数组，使用 (n + mid - 1) / mid 完成每个元素的向上取整并累计。
如果累计和在过程中已经超出 threshold，就可以提前结束返回 false，避免无意义的遍历。

复杂度#

二分查找的搜索空间长度为 max(nums)，时间复杂度为 O(n log max(nums))，空间复杂度为 O(1)。

代码#

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int right = 0;
        for (int n : nums) {
            right = Math.max(right, n);
        }
        int left = 1;

        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (check(nums, threshold, mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean check(int[] nums, int threshold, int divisor) {
        int sum = 0;
        for (int n : nums) {
            sum += (n + divisor - 1) / divisor;
            if (sum > threshold) {
                return false;
            }
        }
        return true;
    }
}

知识边界#

向上取整的写法#

对于正整数 a 和 b，要实现 ceil(a / b)，可以使用公式 (a + b - 1) / b。原因是先给被除数补足到下一个 b 的倍数，再执行整数除法即可实现向上取整。