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

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 math

class 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的除数和是否大于thershold
            aboveSum=0
            for num in nums:
                aboveSum+=math.ceil(num/divisor)
            return aboveSum>threshold
        left,right=1,max(nums)
        while left<=right:
            mid=(right-left)//2+left
            if check(mid):
                left=mid+1
            else:
                right=mid-1
        return left

4.执行结果