1. 題目

給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)正整數(shù) threshold ，你需要選擇一個(gè)正整數(shù)作為除數(shù)，然后將數(shù)組里每個(gè)數(shù)都除以它，并對(duì)除法結(jié)果求和。

請(qǐng)你找出能夠使上述結(jié)果小于等于閾值 threshold 的除數(shù)中 最小 的那個(gè)。

每個(gè)數(shù)除以除數(shù)后都向上取整，比方說 7/3 = 3 ， 10/2 = 5 。

題目保證一定有解。

示例 1： 輸入：nums = [1,2,5,9], threshold = 6 輸出：5 解釋：如果除數(shù)為 1 ，我們可以得到和為 17 （1+2+5+9）。 如果除數(shù)為 4 ，我們可以得到和為 7 (1+1+2+3) 。如果除數(shù)為 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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-the-smallest-divisor-given-a-threshold
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

class Solution { // C++ public:int smallestDivisor(vector<int>& nums, int threshold) {int i, l = 1, r = 1000000, mid, sum;while(l < r){mid = l+((r-l)>>1);sum = 0;for(i = 0; i < nums.size(); ++i)sum += ceil(nums[i]/double(mid));if(sum > threshold)//分母太小了l = mid+1;//放大elser = mid;}return l;} };

76 ms 19.3 MB

class Solution: # py3def smallestDivisor(self, nums: List[int], threshold: int) -> int:l, r = 1, 1000000n = len(nums)while l < r:mid = l+((r-l)>>1)sum = 0for i in range(n):sum += ceil(nums[i]/mid)if sum > threshold:l = mid+1else:r = midreturn l

580 ms 19.2 MB

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1283. 使结果不超过阈值的最小除数（二分查找）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。