题意是这样的，
现在有k种颜色的球（每种颜色球的数量不同，做为输入给你），需要把它们放入最少的袋子。
有两种放法，一种是袋子里面只放一种颜色的球， 这样每个袋子最多放k个，
另外一种是一个袋子里面放不同种类的球，但是如果这样放的话每种球每个袋子里面只能放一个。
换一种说话就是每次袋子要么装同一种颜色的球最多k个，要么装不同种类的球每种只能放一个。
不管怎么放每个袋子最多只能放k个。
首先 先对每种数量大于 k的球单独装袋， 每袋装满 k个。
减掉这些球之后，对Array里剩余的球的数量从大到小排列.
我画了图如下所示，最初我们站在左下角。
如果你站在左下角，则要么你取它所在的那一整行，要么你取它所在的那一整列。
因为这时行和列的数量都一定是小于等于k的，所以一次可以一次取一整行或者一次取一整列。
问题就转换成从图的左下角到图的右上角最少需要多少步。但这张图里有很多个右上角。所以需要sweep一遍找最小值。
但从左下角到其中一个右上角一共有多少步呢？
步数等于这个column的index + ball的数量。
就是column index + 这个column的高度.
换一种表述方式，对于这个右上角的点，他所有左边的点都是自已装一袋， 他所有下面的点都是混装的。
所以一共是index + balls[index]个。 但我们不知道取那个右上角，所以要扫一遍求最小值。
一句话 总结就是要么横着取要么竖着取，看最快要几次取完。
image.png
时间复杂度nlogn, 主要消耗在排序上。
public int getMinBags(int[] balls, int k) {
int count = 0;
// k different balls.
//先把大于k的球全部装袋。每个袋子k个。
//这里有个assumption就是balls的长度一定是k，即使为0也不能省。否则会出bug，或者我们自己补足k位。
for (int i = 0; i < k; i++) {
if (balls[i] >= k) {
count += balls[i] / k;
balls[i] %= k;
}
}
Arrays.sort(balls);
// reverse , 应该从大到小排列
int l = 0, r = k - 1;
while ( l < r) swap(balls, l++, r--);
int min = k;
for (int i = 0; i < k; i++) {
min = Math.min(min, i + balls[i]);
if (balls[i] == 0) break; //这句话写不写都没影响
}
return min + count; //结果是min + 之前装满的袋子。
}
private void swap(int array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = array[i];
}
这题没什么意思，纯考智商，观察能力，有什么算法在里面吗？？？
网友评论