重新分装苹果
难度:
标签:
题目描述
You are given an array apple of size n and an array capacity of size m.
There are n packs where the ith pack contains apple[i] apples. There are m boxes as well, and the ith box has a capacity of capacity[i] apples.
Return the minimum number of boxes you need to select to redistribute these n packs of apples into boxes.
Note that, apples from the same pack can be distributed into different boxes.
Example 1:
Input: apple = [1,3,2], capacity = [4,3,1,5,2] Output: 2 Explanation: We will use boxes with capacities 4 and 5. It is possible to distribute the apples as the total capacity is greater than or equal to the total number of apples.
Example 2:
Input: apple = [5,5,5], capacity = [2,4,2,7] Output: 4 Explanation: We will need to use all the boxes.
Constraints:
1 <= n == apple.length <= 501 <= m == capacity.length <= 501 <= apple[i], capacity[i] <= 50- The input is generated such that it's possible to redistribute packs of apples into boxes.
代码结果
运行时间: 19 ms, 内存: 16.1 MB
/*
* 思路：
* 1. 将容量数组按降序排序。
* 2. 计算所有苹果的总数。
* 3. 遍历容量数组并逐一使用容量最大的箱子装苹果，直到装完所有苹果。
* 4. 返回使用的箱子数量。
*/
import java.util.Arrays;
public class Solution {
public int minBoxes(int[] apple, int[] capacity) {
Arrays.sort(capacity);
int totalApples = Arrays.stream(apple).sum();
int[] boxCount = {0};
int[] currentCapacity = {0};
Arrays.stream(capacity)
.boxed()
.sorted((a, b) -> b - a)
.takeWhile(cap -> {
currentCapacity[0] += cap;
boxCount[0]++;
return currentCapacity[0] < totalApples;
})
.count();
return boxCount[0];
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] apple = {1, 3, 2};
int[] capacity = {4, 3, 1, 5, 2};
System.out.println(sol.minBoxes(apple, capacity)); // 输出：2
}
}解释
方法:
该题解的主要思路是首先计算所有包裹中苹果的总数，然后将箱子的容量数组进行降序排序。通过遍历排序后的箱子容量数组，逐一从苹果总数中减去每个箱子的容量，直到苹果总数小于或等于零。这样，我们就能得到所需的最小箱子数量。该方法的核心在于优先使用容量大的箱子，以最大化每次装箱的苹果数量，从而减少所需箱子的数量。
时间复杂度:
O(m log m)
空间复杂度:
O(m)
代码细节讲解
🦆
算法中苹果总数 `t` 是否可能超出 `int` 类型的范围，导致计算错误？
▷🦆
在箱子容量数组 `capacity` 降序排序后，如何保证这种排序方式总是得到最优解？
▷🦆
如果存在某些箱子的容量为 0，算法是否还能正确处理？
▷