如何将有序的整数列表划分为大小均匀的子列表？

Question

有没有人有一个很好的算法来获取有序的整数列表,即:
[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] ]

要求是每个子列表都是有序的并且尺寸尽可能相似.

Answer 1

均匀拆分列表意味着您将拥有两种大小的列表 - 大小为S和S + 1.

使用N个子列表和原始X元素,您将获得:

(E/N)较小子列表(S)中的元素数量(X/N),X%N是较大子列表(S + 1)的数量.

然后迭代原始数组,并(看你的例子)创建小列表第一.

这样的事情可能是:

 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;
}