1.题目基本信息

1.1.题目描述

给你一个整数数组 nums 和一个正整数 threshold ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。

请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。

每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。

题目保证一定有解。

1.2.题目地址

https://leetcode.cn/problems/find-the-smallest-divisor-given-a-threshold/description/

2.解题方法

2.1.解题思路

选择的除数越大，除数和也会越小，这是一个递减的过程，所以可以使用二分查找的方法

2.2.解题步骤

第一步，初始化除数的边界值，最小为1，最大为nums中的最大值

第二步，定义check函数。判断在divisor除数的条件下，其除数的向上取整的和是否大于threshold

第三步，红蓝染色法特征定义。红：在除数mid下，除数和大于threshold的项，蓝：在除数mid下，除数和小于等于threshold的项。左闭右闭：left-1始终指向红色，righ始终指向蓝色。最终的left/right+1为最终题解

3.解题代码

Python代码

import mathclass Solution:def smallestDivisor(self, nums: List[int], threshold: int) -> int:# 选择的除数越大，除数和也会越小，这是一个递减的过程，所以可以使用二分查找的方法# 第一步，初始化除数的边界值，最小为1，最大为nums中的最大值# 第二步，定义check函数。判断在divisor除数的条件下，其除数的向上取整的和是否大于threshold# 第三步，红蓝染色法特征定义。红：在除数mid下，除数和大于threshold的项，蓝：在除数mid下，除数和小于等于threshold的项。左闭右闭：left-1始终指向红色，righ始终指向蓝色。最终的left/right+1为最终题解def check(divisor):# 判断除数divisor的除数和是否大于thersholdaboveSum=0for num in nums:aboveSum+=math.ceil(num/divisor)return aboveSum>thresholdleft,right=1,max(nums)while left<=right:mid=(right-left)//2+leftif check(mid):left=mid+1else:right=mid-1return left

4.执行结果