需求:假设文件夹内有多个小文件需要拆分给多个服务器处理,拆分尽量均匀顺序不能乱。
入参list 是需要分割的数组,groups 是需要分割多少份,limits 是函数返回第几份。
思路是,数组长度除groups ,余数中每一个元素均匀分配到组。因为groups一定大于等于余数,组的pageSize加1,一定可全部分担所有余数。
1、 list.length % group == 0 是刚好均分,那么 pageSize = list.length / group
2、(list.length % group)>= groupLimit,说明还有余数没有均分完成,所以 pageSize = (list.length / group) + 1
3、有余数且余数均分完成,skip 要等于之前均分余数的组长度加上无需均分余数的组长度
public static String[] groupFilter(String[] list, String groups, String groupLimits) {
if (list == null || list.length == 0) {
return list;
}
if (!NumberUtils.isParsable(groups) || !NumberUtils.isParsable(groupLimits)) {
return list;
}
int group = Integer.parseInt(groups);
int groupLimit = Integer.parseInt(groupLimits);
if (group <= 1 || groupLimit <= 0 || groupLimit > group) {
return list;
}
int pageSize = list.length / group;
int mod = list.length % group;
int skip = 0;
if(mod == 0){//刚好均分
skip = pageSize * (groupLimit - 1);
}else if (mod >= groupLimit) {//有余数均分余数
pageSize = pageSize + 1;
skip = pageSize * (groupLimit - 1);
} else {//有余数且余数均分完成
skip = ((pageSize + 1) * mod) + (pageSize * (groupLimit - mod - 1));
}
return Arrays.stream(list).sorted().skip(skip).limit(pageSize).toArray(String[]::new);
}
一个整数数组,长度为n,将其分为m 份,使各份的和相等,求m 的最大值
比如数组:{3,2,4,3,6}
m=1,可以分成{3,2,4,3,6} ;
m=2,可以分成{3,6}{2,4,3}
m=3,可以分成{3,3}{2,4}{6}
所以m 的最大值为3
- 思路:
- 条件1: 均匀拆分
- 推论1: 对每个分组求和一定分别相等 , 分组数量*每个分组的和 = 原数组和
- 推论2: 每个分组的和 = 原数组和/分组数量,不能出现余数
- 推论3:分组数量最多一定是原数组的长度,可以从最大开始循环
- 根据三条推论,有如下程序。
@Test
private static void test3() {
int[] a = { 3, 2, 4, 3, 6 };
int sum = Arrays.stream(a).sum();
//遍历所有可能的分组个数
for (int quantity = a.length; quantity > 1; quantity--) {
//无法均分
if (sum % quantity != 0)
continue;
//每个组的数值和
int groupSum = sum / quantity;
//当前组未分配的数值
int groupUnassigned = sum / quantity;
if (test(a, new int[a.length], quantity, groupSum, groupUnassigned, 1)) {
System.out.println("The Max m is:" + quantity);
break;
}
}
}
/**
*
* @param a 原数组
* @param allocate 记录已经分配的元素
* @param quantity 分组总个数
* @param groupSum 每个组的数值和
* @param groupUnassigned 当前组未分配的数值
* @param groupLimit 当前分组位移
* @return false 分配失败, true 分配成功
*/
private static boolean test(int[] a, int[] allocate, int quantity, int groupSum,
int groupUnassigned, int groupLimit) {
// 说明加上当前元素后数小组元素的和过大
if (groupUnassigned < 0) {
return false;
}
//当前组分配完成
if (groupUnassigned == 0) {
groupLimit++;
groupUnassigned = groupSum;
//所有组分配完成
if (groupLimit == quantity + 1) {
return true;
}
}
for (int i = 0; i < allocate.length; i++) {
//元素已经被分配了
if (allocate[i] != 0)
continue;
//预分配
allocate[i] = groupLimit;
if (test(a, allocate, quantity, groupSum, groupUnassigned - a[i], groupLimit))
return true;
// 当前元素分配失败,置回初始状态
allocate[i] = 0;
}
return false;
}