如何将有序的整数列表划分为大小均匀的子列表？
有没有人有一个很好的算法来获取整数的有序列表，即：
[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]
要求是每个子列表都是有序的并且尺寸尽可能相似。
均匀拆分列表意味着您将拥有两种大小的列表 – 大小为S和S + 1。
使用N个子列表和原始X元素，您将获得：
floor（X / N）在较小子列表（S）中的元素数量，并且X％N是较大子列表（S + 1）的数量。
然后迭代原始数组，并（看你的例子）创建小列表第一。
这样的事情可能是：
private static List splitOrderedDurationsIntoIntervals(Integer[] durations, int numberOfIntervals) { int sizeOfSmallSublists = durations.length / numberOfIntervals; int sizeOfLargeSublists = sizeOfSmallSublists + 1; int numberOfLargeSublists = durations.length % numberOfIntervals; int numberOfSmallSublists = numberOfIntervals - numberOfLargeSublists; List 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; } 这是我自己的递归解决方案，受到合并排序和广度优先树遍历的启发：
private static void splitOrderedDurationsIntoIntervals(Integer[] durations, List intervals, int numberOfInterals) { int middle = durations.length / 2; Integer[] lowerHalf = Arrays.copyOfRange(durations, 0, middle); Integer[] upperHalf = Arrays.copyOfRange(durations, middle, durations.length); if (lowerHalf.length > upperHalf.length) { intervals.add(lowerHalf); intervals.add(upperHalf); } else { intervals.add(upperHalf); intervals.add(lowerHalf); } if (intervals.size() < numberOfIntervals) { int largestElementLength = intervals.get(0).length; if (largestElementLength > 1) { Integer[] duration = intervals.remove(0); splitOrderedDurationsIntoIntervals(duration, intervals); } } }
我希望有人可能会建议迭代解决方案。
这是 Python的解决方案。 您可以将其转换为Java，您需要一种方法来获取一个列表然后返回它。 但是，您不能使用生成器方法，但可以将每个子列表附加到新列表中。
伪…
private static void splitOrderedDurationsIntoIntervals(Integer[] durations, List intervals, int numberOfInterals) { int num_per_interval = Math.floor(durations.length / numberOfInterals); int i; int idx; // make sure you have somewhere to put the results for (i = 0; i < numberOfInterals; i++) intervals[i] = new Integer[]; // run once through the list and put them in the right sub-list for (i = 0; i < durations.length; i++) { idx = Math.floor(i / num_per_interval); intervals[idx].add(durations[i]); } }
该代码需要整理一下，但我相信你明白了。 此外，我怀疑大小不均匀的间隔列表将在结束时而不是在开始时。 如果你真的想要这样，你可以通过颠倒循环的顺序来做到这一点。
这应该是一个更迭代的答案。
public static void splitList(List startList, List> resultList, int subListNumber) { final int subListSize = startList.size() / subListNumber; int index = 0; int stopIndex = subListSize; for (int i = subListNumber; i > 0; i--) { resultList.add(new ArrayList (startList.subList(index, stopIndex))); index = stopIndex; stopIndex = (index + subListSize > startList.size()) ? startList.size() : index + subListSize; } }
你可能会考虑这样的事情：
public static int[][] divide(int[] initialList, int sublistCount) { if (initialList == null) throw new NullPointerException("initialList"); if (sublistCount < 1) throw new IllegalArgumentException("sublistCount must be greater than 0."); // without remainder, length / # lists will always be the minimum // number of items in a given subset int min = initialList.length / sublistCount; // without remainer, this algorithm determines the maximum number // of items in a given subset. example: in a 15-item sample, // with 4 subsets, we get a min of 3 (15 / 4 = 3r3), and // 15 + 3 - 1 = 17. 17 / 4 = 4r1. // in a 16-item sample, min = 4, and 16 + 4 - 1 = 19. 19 / 4 = 4r3. // The -1 is required in samples in which the max and min are the same. int max = (initialList.length + min - 1) / sublistCount; // this is the meat and potatoes of the algorithm. here we determine // how many lists have the min count and the max count. we start out // with all at max and work our way down. int sublistsHandledByMax = sublistCount; int sublistsHandledByMin = 0; while ((sublistsHandledByMax * max) + (sublistsHandledByMin * min) != initialList.length) { sublistsHandledByMax--; sublistsHandledByMin++; } // now we copy the items into their new sublists. int[][] items = new int[sublistCount][]; int currentInputIndex = 0; for (int listIndex = 0; listIndex < sublistCount; listIndex++) { if (listIndex < sublistsHandledByMin) items[listIndex] = new int[min]; else items[listIndex] = new int[max]; // there's probably a better way to do array copies now. // it's been a while since I did Java :) System.arraycopy(initialList, currentInputIndex, items[listIndex], 0, items[listIndex].length); currentInputIndex += items[listIndex].length; } return items; }
这还不是很完美 - 当我试图通过10个子列表传递一个18项数组时，我进入了一个无限循环（我想）。 我认为当min == 1时算法会崩溃。
这应该相当快。 祝好运 ：）