本文记录最近与朋友聊过的算法实例：给定一堆带重量的货物，计算最少需要的货车数量。
业务算法系列：收录业务系统开发中真实遇到的算法
题目描述：
给定一个int[]，weights [100,300]范围，每个元素表示货物重量的数组
求装完给定货物最少的车辆数
限制：每个货物最多能装300的货物
货物重量数组长度为n，货物重量区间为m
过了两天已经想不起我最开始的错误思路了，所以本文就聚焦来看正确思路吧。
关于这道题跟湧哥聊了一轮，他给了我一个解题的窍门：针对这种题目，对于入参有常数级的限制，因此可以考虑一些特定的做法，比如对数据排序可以考虑桶排序，对于数据查找可以粗暴遍历（因为复杂度是常数级）。
正确的解题思路：#
- 对货物按照重量排序；
- 针对每辆车，尽可能找当前剩余最重且当前车能装的下的货物（贪心）；
- 重复这个过程，一直每辆车都装满或者装不下剩余货物中最轻的；
第一步：排序#
对于排序，最粗暴的方式就是使用快排，针对本题，由于货物重量区间为[100,300]，是一个常量区间，因此可以使用桶排序，使用一个201长度的数组即可统计货物重量以及数量，同时一次桶排序仅需遍历一次入参数组，时间复杂度为O(n)。
在排序这一步，桶排序优于快排。
第二步：找当前装的下最重的货物#
本题中一辆车最多能装三个100，因此查找当前装得下最重的货物可以粗暴遍历，从当前车辆剩余容量开始逐个遍历即可，最多遍历201次。
拓展：如果入参可以很大，这里的查找可以考虑二分法，这样可以保证较大数据集的时候，查找效率最高。
第三步：重复装车#
这一步只要维护好边界，能够及时跳出循环即可。
代码实现#
思路描述完了，下面展示我两种思路下的代码实现：
桶排序+遍历查找#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
/**
* 观察题目给定的条件，发现货物重量区间为 [100, 300]，是一个常数级别的区间，因此我们可以尝试两个操作：
* 1. 给定的重量排序，可以使用桶排序，排序的复杂度能达到O(n)，要优于快排这种方案；
* 2. 每辆车去找当前能装得下的最大货物时，可直接遍历查找（因为逐个遍历也就是O(201)的复杂度，是一个常数级复杂度）；
*/
public static class BucketSortSolution {
public int findMinimumQuantityOfCars(int[] weights) {
// 排序后的桶，维护货物重量->货物数量
// 复杂度：O(n)
// 一共n个货物
int bucketN = 300 - 100 + 1;
int[] weight2Cnt = new int[bucketN];
for (int weight : weights) {
weight2Cnt[weight - 100]++;
}
int ans = 0;
while (true) {
// 标记当前车辆有无货物可装，一辆车最多装3个货
int carWeightCnt = 3;
// 当前车辆剩余可装容量
int remainWeight = 300;
// 每辆车尽可能装满
// 从大的货物开始装
for (int i = remainWeight - 100; i >= 0; i--) {
int currWeight = i + 100;
if (remainWeight < currWeight || weight2Cnt[i] == 0) {
// 当前货物太重了，看下一个比较轻的
// 当前重量没有货物
continue;
}
while (remainWeight >= currWeight && weight2Cnt[i] > 0) {
remainWeight -= currWeight;
weight2Cnt[i]--;
carWeightCnt--;
}
}
if (carWeightCnt == 3) {
// 已经没有货物了
break;
}
ans++;
}
return ans;
}
}
|
复杂度#
空间复杂度，使用了一个额外的数组维护重量对应数量，复杂度O(m)。
时间复杂度，排序遍历一次入参数组，每辆车查找遍历x次排序数组（x为一个常量），时间复杂度最大为O(m*n)。
红黑树（或者可以考虑java中的跳表结构）#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
/**
* 使用有序集合（树、跳表）的方案思路：
* 1. 使用红黑树记录每个重量对应的货物数量；
* 2. 每辆车从当前剩余
*/
public static class BinarySearchCollectionSolution {
/**
* 整体复杂度：O(n*logn)
* 限制：每辆车可以装载最大300的货物
*
* @param weights [100,300]范围，每个元素表示货物重量的数组
* @return 求装完给定货物最少的车辆数
*/
public int findMinimumQuantityOfCars(int[] weights) {
int ans = 0;
// 每个重量的货 对应 数量
TreeMap<Integer, Integer> weight2Count = new TreeMap<>(Comparator.naturalOrder());
// 树形成复杂度 O(n*logn)
for (int weight : weights) {
weight2Count.put(weight, weight2Count.getOrDefault(weight, 0) + 1);
}
// 每辆车先选中一个当前最大的货，重量x，然后去找小于且最接近(当前剩余容量-x)的货，如果此时(当前剩余容量-x)小于100则装下一辆
// 每一轮选中某个货物后，从treemap有序结构中移除货物计数
while (true) {
if (weight2Count.size() == 0) {
break;
}
// 从最重的货物开始装
// 获取最大值复杂度 O(1)
Integer maxWeight = weight2Count.lastKey();
// 更新最重货物量
updateTargetWeightCount(weight2Count, maxWeight);
if (weight2Count.size() == 0) {
break;
}
int remainWeight = 300 - maxWeight;
while (weight2Count.size() > 0 && weight2Count.firstKey() <= remainWeight) {
// 这里使用树形结构查询，二分法复杂度 O(logn)
Integer maxLowerWeight = weight2Count.floorKey(remainWeight);
// 更新 小于且最接近(当前剩余容量-x)的货量
updateTargetWeightCount(weight2Count, maxLowerWeight);
remainWeight -= maxLowerWeight;
}
ans++;
}
return ans;
}
// 更新某个key O(1)
private void updateTargetWeightCount(TreeMap<Integer, Integer> weight2Count, Integer maxLowerWeight) {
Integer maxLowerWeightCount = weight2Count.get(maxLowerWeight);
if (maxLowerWeightCount - 1 > 0) {
weight2Count.put(maxLowerWeight, maxLowerWeightCount - 1);
} else {
weight2Count.remove(maxLowerWeight);
}
}
}
|
复杂度#
空间复杂度，使用了一个额外的树形map维护货物重量，复杂度O(n)。
时间复杂度，每次查找通过二分法找到小于等于特定重量的元素，时间复杂度O(logn)，这个过程最多查找n次，因此整体时间复杂度O(n*logn)。
对于题目给定的较小数据集，桶排序+遍历查找是更加直观的解法，同时湧哥几分钟内就实现了一版，他能够快速找到这道题给定条件的突破点并且实现，这点给了我启发：对于特定条件要有条件反射，小数据集有对应的套路。
而对于更大或者更通用的数据集，则可以按照我实现的树结构、跳表结构来解题。
两种算法各有优劣，对于本题货车装货的实际场景，桶排序的方式更高效，只有当m n变量变的更大时，二分的解法才更高效。