java 均匀分割数组或集合

需求:假设文件夹内有多个小文件需要拆分给多个服务器处理,拆分尽量均匀顺序不能乱。

入参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;
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,922评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,591评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,546评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,467评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,553评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,580评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,588评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,334评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,780评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,092评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,270评论 1 344
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,925评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,573评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,194评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,437评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,154评论 2 366
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,127评论 2 352

推荐阅读更多精彩内容