合法分组的最少组数
难度:
标签:
题目描述
You are given a collection of numbered balls and instructed to sort them into boxes for a nearly balanced distribution. There are two rules you must follow:
- Balls with the same box must have the same value. But, if you have more than one ball with the same number, you can put them in different boxes.
- The biggest box can only have one more ball than the smallest box.
Return the fewest number of boxes to sort these balls following these rules.
Example 1:
Input: balls = [3,2,3,2,3]
Output: 2
Explanation:
We can sort balls into boxes as follows:
[3,3,3][2,2]
The size difference between the two boxes doesn't exceed one.
Example 2:
Input: balls = [10,10,10,3,1,1]
Output: 4
Explanation:
We can sort balls into boxes as follows:
[10][10,10][3][1,1]
You can't use fewer than four boxes while still following the rules. For example, putting all three balls numbered 10 in one box would break the rule about the maximum size difference between boxes.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109
代码结果
运行时间: 84 ms, 内存: 38.7 MB
/*
* 思路：
* 1. 使用流的方式统计每种编号球的数量。
* 2. 计算每种编号球分配到的最小盒子数。
* 3. 保证最大盒子的球数比最小盒子多的数目不超过1。
*/
import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;
public class Solution {
public int minBoxes(int[] balls) {
Map<Integer, Long> countMap = Arrays.stream(balls)
.boxed()
.collect(Collectors.groupingBy(ball -> ball, Collectors.counting()));
return countMap.values().stream()
.mapToInt(count -> (int) ((count + 1) / 2))
.max()
.orElse(0);
}
}解释
方法:
时间复杂度:
空间复杂度: