class Solution {
public:
int smallestDivisor(vector<int>& nums, int threshold) {
}
};
1283. 使结果不超过阈值的最小除数
给你一个整数数组 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^41 <= nums[i] <= 10^6nums.length <= threshold <= 10^6原站题解
golang 解法, 执行用时: 28 ms, 内存消耗: 6.7 MB, 提交时间: 2023-09-27 11:12:43
func smallestDivisor(nums []int, threshold int) int {
return sort.Search(1e6+1, func(i int) bool {
i++
c := 0
for _, v := range nums {
if v % i != 0 {
c++
}
c += v / i
}
return c <= threshold
}) + 1
}
java 解法, 执行用时: 5 ms, 内存消耗: 46.4 MB, 提交时间: 2023-09-27 11:11:43
class Solution {
public int smallestDivisor(int[] nums, int threshold) {
int L = 1, R = 1_000_000;
while(L < R){
int mid = L + (R - L) / 2;
if(!possible(nums, mid, threshold)){
L = mid + 1;
}else{
R = mid;
}
}
return L;
}
public boolean possible(int[] nums, int divisor, int threshold){
int count = 0;
for(int num : nums){
count += (num - 1) / divisor + 1;
}
return count <= threshold;
}
}
cpp 解法, 执行用时: 36 ms, 内存消耗: 22.3 MB, 提交时间: 2023-09-27 11:10:44
class Solution {
public:
int smallestDivisor(vector<int>& nums, int threshold) {
int l = 1, r = *max_element(nums.begin(), nums.end());
int ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
int total = 0;
for (int num: nums) {
total += (num - 1) / mid + 1;
}
if (total <= threshold) {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
return ans;
}
};
python3 解法, 执行用时: 296 ms, 内存消耗: 20.6 MB, 提交时间: 2023-09-27 11:10:31
class Solution:
def smallestDivisor(self, nums: List[int], threshold: int) -> int:
l, r, ans = 1, max(nums) + 1, -1
while l <= r:
mid = (l + r) // 2
total = sum((x - 1) // mid + 1 for x in nums)
if total <= threshold:
ans = mid
r = mid - 1
else:
l = mid + 1
return ans