题目

给你一个整数数组 nums，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations。

你可以进行如下操作至多 maxOperations 次：

选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有正整数个球。
比如一个袋子里有 5 个球，可以分成 1 和 4，或者 2 和 3。

你的开销是单个袋子里球数目的最大值，你想要最小化开销。请返回最小开销。

示例 1

输入：nums = [9], maxOperations = 2
输出：3
解释：[9] -> [6,3] -> [3,3,3]，最大值为 3。

示例 2

输入：nums = [2,4,8,2], maxOperations = 4
输出：2
解释：最终可分为 [2,2,2,2,2,2,2,2]，最大值为 2。

示例 3

输入：nums = [7,17], maxOperations = 2
输出：7

解题思路

这道题可以使用二分查找来解决：

  1. 题目分析：

    • 我们需要找到一个最小值 x，使得所有袋子里的球数都不超过 x
    • 对于每个袋子，如果球数超过 x，需要进行分割操作
    • 分割操作次数不能超过 maxOperations

  2. 二分查找思路：

    • 对于给定的目标值 x，可以计算需要多少次操作才能使所有袋子的球数 ≤ x
    • 如果操作次数 ≤ maxOperations，说明 x 可能还可以更小
    • 如果操作次数 > maxOperations，说明 x 必须更大

  3. 关键点：

    • 二分查找的左边界是 1
    • 右边界是数组中的最大值
    • 对于每个 x，计算需要的操作次数

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        def check(mid: int) -> bool:
            # 计算以mid为目标值时需要的操作次数
            operations = sum((num - 1) // mid for num in nums)
            return operations <= maxOperations


        left, right = 1, max(nums)
        # 二分查找
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                # 如果当前的mid可行，mid当前大，可以尝试更小的值
                right = mid
            else:
                # 如果当前的mid不可行，mid 当前太小了，必须尝试更大的值
                left = mid + 1

        return left

代码解释

  1. check(mid)函数：

    • 计算将所有球数控制在mid以下需要的操作次数
    • 对于每个袋子，需要的操作次数是 (num-1) // mid
    • 如果总操作次数 ≤ maxOperations，返回True

  2. 二分查找过程：

    • 初始范围：[1, max(nums)]
    • 每次取中间值mid
    • 根据check(mid)的结果缩小范围
    • 最终找到满足条件的最小值

复杂度分析

  • 时间复杂度：O(n * log M)

    • n 是数组长度
    • M 是数组中的最大值
    • 二分查找需要 log M 次迭代
    • 每次迭代需要 O(n) 时间计算操作次数

  • 空间复杂度：O(1)

    • 只使用了常数额外空间

总结

这是一道典型的二分查找应用题。关键在于：

  1. 将问题转化为判定性问题
  2. 设计合适的判定函数
  3. 正确处理二分查找的边界条件

关键代码详解

1
operations = sum((num - 1) // mid for num in nums)

这行代码计算需要多少次操作才能使所有袋子的球数不超过mid。让我们逐部分分析：

  1. (num - 1) // mid 的含义：

    • 假设一个袋子有 num 个球，目标是将其分成若干个不超过 mid 的小袋
    • 例如：num = 9, mid = 3
    • (9-1) // 3 = 8 // 3 = 2，表示需要2次操作
    • 第一次：9 -> [3,6]
    • 第二次：6 -> [3,3]
    • 最终：[3,3,3]

  2. 为什么是 (num - 1) // mid：

    • 如果 num = 7, mid = 3
    • (7-1) // 3 = 6 // 3 = 2 次操作
    • 第一次：7 -> [3,4]
    • 第二次：4 -> [3,1]
    • 最终：[3,3,1]

  3. 整数除法 // 的作用：

    • 向下取整，确保得到最少需要的操作次数
    • 例如：5/2 = 2.5，而 5//2 = 2

  4. 列表推导式 for num in nums：

    • 对数组中的每个数字都进行上述计算

  5. sum() 函数：

    • 将所有需要的操作次数加总
    • 得到处理整个数组需要的总操作次数

示例：

1
2
3
4
5
6
nums = [9, 5]
mid = 3

# 对于 9：(9-1)//3 = 8//3 = 2 次操作
# 对于 5：(5-1)//3 = 4//3 = 1 次操作
# 总操作次数：2 + 1 = 3