我如何划分整数的有序列表分为大小均匀子列表？ [英] How do I divide an ordered list of integers into evenly sized sublists?

问题描述

没有任何人有一个良好的算法取整数的有序列表，即：
[1，3，6，7，8，10，11，13，14，17，19，23，25，27，28]

Does anyone have a good algorithm for taking an ordered list of integers, i.e.:
[1, 3, 6, 7, 8, 10, 11, 13, 14, 17, 19, 23, 25, 27, 28]

成的大小均匀的有序子列表的给定数量，即4将是：
[1，3,6] [7，8，10，11]，[13，14，17，19] [23，25，27，28]

into a given number of evenly sized ordered sublists, i.e. for 4 it will be:
[1, 3, 6] [7, 8, 10, 11] [13, 14, 17, 19] [23, 25, 27, 28]

的要求是每个子列表的排序和大小尽可能相似。

The requirement being that each of the sublists are ordered and as similar in size as possible.

推荐答案

拆分名单均匀意味着你将有两种型号列表 - 大小S和S + 1

Splitting the lists evenly means you will have two sizes of lists - size S and S+1.

用N子列表，并在原始x元素，你会得到：

With N sublists, and X elements in the original, you would get:

地板（X / N）的数目中较小的子列表（S）的元素，以及X％N是较大的子列表（S + 1）的数目。

floor(X/N) number of elements in the smaller sublists (S), and X % N is the number of larger sublists (S+1).

然后遍历原始数组，并（在看你的例子）创建的小名单第一。

Then iterate over the original array, and (looking at your example) creating small lists firsts.

事情是这样的，也许：

 private static List<Integer[]> splitOrderedDurationsIntoIntervals(Integer[] durations, int numberOfIntervals) {

    int sizeOfSmallSublists = durations.length / numberOfIntervals;
    int sizeOfLargeSublists = sizeOfSmallSublists + 1;
    int numberOfLargeSublists = durations.length % numberOfIntervals;
    int numberOfSmallSublists = numberOfIntervals - numberOfLargeSublists;

    List<Integer[]> sublists = new ArrayList(numberOfIntervals);
    int numberOfElementsHandled = 0;
    for (int i = 0; i < numberOfIntervals; i++) {
        int size = i < numberOfSmallSublists ? sizeOfSmallSublists : sizeOfLargeSublists;
        Integer[] sublist = new Integer[size];
        System.arraycopy(durations, numberOfElementsHandled, sublist, 0, size);
        sublists.add(sublist);
        numberOfElementsHandled += size;
    }
    return sublists;
}

这篇关于我如何划分整数的有序列表分为大小均匀子列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！