给你一个整数数组 nums 和一个正整数 threshold ,你需要选择一个正整数作为除数,然后将数组里每个数都除以它,并对除法结果求和。
请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。
每个数除以除数后都向上取整,比方说 7/3 = 3 , 10/2 = 5 。
题目保证一定有解。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-the-smallest-divisor-given-a-threshold
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
import java.util.Arrays;
class Solution {
private int getSum(int[] nums, int divide) {
int ans = 0;
for (int num : nums) {
if (num % divide == 0) {
ans += num / divide;
} else {
ans += num / divide + 1;
}
}
return ans;
}
public int smallestDivisor(int[] nums, int threshold) {
int max = Arrays.stream(nums).max().getAsInt();
int left = 1, right = max;
int ans = 1;
while (left <= right) {
int mid = (left + right) >> 1;
if (getSum(nums, mid) <= threshold) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}