Question

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

English Version

题目描述

给你一个整数数组 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

 

提示：

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

解法

方法一：二分查找

我们注意到，对于一个数字 $v$，如果将 $nums$ 中的每个数字都除以 $v$ 的结果之和小于等于 $threshold$，那么所有大于 $v$ 的值都满足条件。这存在着单调性，因此我们可以使用二分查找的方法找到最小的满足条件的 $v$。

我们定义二分查找的左边界 $l=1$, $r=\max(nums)$，每次取 $mid=(l+r)/2$，计算 $nums$ 中每个数字除以 $mid$ 的结果之和 $s$，如果 $s$ 小于等于 $threshold$，那么说明 $mid$ 满足条件，我们将 $r$ 更新为 $mid$，否则将 $l$ 更新为 $mid+1$。

最后返回 $l$ 即可。

时间复杂度 $O(n \times \log M)$，其中 $n$ 是数组 $nums$ 的长度，而 $M$ 是数组 $nums$ 中的最大值。空间复杂度 $O(1)$。

class Solution:
  def smallestDivisor(self, nums: List[int], threshold: int) -> int:
    l, r = 1, max(nums)
    while l < r:
      mid = (l + r) >> 1
      if sum((x + mid - 1) // mid for x in nums) <= threshold:
        r = mid
      else:
        l = mid + 1
    return l

class Solution:
  def smallestDivisor(self, nums: List[int], threshold: int) -> int:
    def f(v: int) -> bool:
      v += 1
      return sum((x + v - 1) // v for x in nums) <= threshold

    return bisect_left(range(max(nums)), True, key=f) + 1

class Solution {
  public int smallestDivisor(int[] nums, int threshold) {
    int l = 1, r = 1000000;
    while (l < r) {
      int mid = (l + r) >> 1;
      int s = 0;
      for (int x : nums) {
        s += (x + mid - 1) / mid;
      }
      if (s <= threshold) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

class Solution {
public:
  int smallestDivisor(vector<int>& nums, int threshold) {
    int l = 1;
    int r = *max_element(nums.begin(), nums.end());
    while (l < r) {
      int mid = (l + r) >> 1;
      int s = 0;
      for (int x : nums) {
        s += (x + mid - 1) / mid;
      }
      if (s <= threshold) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
};

func smallestDivisor(nums []int, threshold int) int {
  return sort.Search(1000000, func(v int) bool {
    v++
    s := 0
    for _, x := range nums {
      s += (x + v - 1) / v
    }
    return s <= threshold
  }) + 1
}

function smallestDivisor(nums: number[], threshold: number): number {
  let l = 1;
  let r = Math.max(...nums);
  while (l < r) {
    const mid = (l + r) >> 1;
    let s = 0;
    for (const x of nums) {
      s += Math.ceil(x / mid);
    }
    if (s <= threshold) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return l;
}

/**
 * @param {number[]} nums
 * @param {number} threshold
 * @return {number}
 */
var smallestDivisor = function (nums, threshold) {
  let l = 1;
  let r = Math.max(...nums);
  while (l < r) {
    const mid = (l + r) >> 1;
    let s = 0;
    for (const x of nums) {
      s += Math.ceil(x / mid);
    }
    if (s <= threshold) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return l;
};

public class Solution {
  public int SmallestDivisor(int[] nums, int threshold) {
    int l = 1;
    int r = nums.Max();
    while (l < r) {
      int mid = (l + r) >> 1;
      int s = 0;
      foreach (int x in nums) {
        s += (x + mid - 1) / mid;
      }
      if (s <= threshold) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}