arrays - 如何将数组划分为 K 个子数组，以使所有子数组中重复元素的数量之和最小？

Question

例如，让数组为 A={1,1,2,1,2}和 K=3 . A可分为{1} , {1,2}和 {1,2} .因此，这些子数组中重复元素的数量为 0、0 和 0。因此，它们的总和为 0。

Answer 1

这是一个相当有趣的挑战。我用 java 来说明我的方法。
将问题分成几部分
我已将整个问题拆分为较小的部分:

我们需要根据分割大小为子阵列设置存储

子数组应该包含相同数量的元素，除非有余数(例如 10 elements 拆分成 k = 3 子数组，导致数组长度为: 3, 3, 4 )

以这样的方式将元素拆分到子数组上，使得重复项最少

1 + 2 - 将数组分成相等的部分
我已经用 array of length 10 做了这个例子和 k = 3 .子数组将为 length 3, 3 and 4由于除法给出的余数。
在代码片段中，我确保用 0 填充数组并且会有 0 to 1每个子数组的额外元素。如果有余数，多余的元素将在所有子数组上拆分。
在我的示例中，我使用了 array with length of 13和 k = 3所以它看起来像这样:

[[0, 0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

3 - 减少重复的策略
我想我们可以从分析给定的数组开始。我们可以通过计数找出每个数字存在的次数。一旦我们知道这些数字存在多少次，我们就可以按值对映射进行排序，最终得到一个包含每个数字出现次数并从出现次数最多的映射开始。
在我的例子中:

1=4 // contains 1 exactly 4 times
2=4 // contains 2 exactly 4 times
3=3 // ...
4=1
5=1

我们从中得到什么？好吧，我们肯定知道，我们不想要所有这些 1 s 在同一个子数组中，因此我们的想法是将所有子数组上的所有出现均分。如果我们最终像 4x 1和 4x 2和 k = 3 (如上例所示)然后我们可以放一个 1和 2进入每个子数组。这给我们留下了 1 个副本(一个额外的 1 和一个额外的 2)。
在我的例子中，这看起来像:

[[1, 2, 3, 4, 5], [1, 2, 3, 0], [1, 2, 3, 0]]
// 1 used 3 times => 1 duplicate
// 2 used 3 times => 1 duplicate
// 3 used 3 times => ok
// 4 used 1 time  => ok
// 5 used 1 time  => ok

为此，我们遍历出现映射，添加键并跟踪我们可以使用的剩余数字(在代码片段中，这是使用映射)。
我们可以对每个键都这样做，直到我们只剩下重复项为止。此时子数组只包含唯一的数字。现在对于重复项，我们可以再次重复整个过程，并在尚未完全填充的子数组上将它们平均拆分。
最后它看起来像这样:

// the duplicate 1 got placed in the second subarray
// the duplicate 2 got placed in the third subarray
[[1, 2, 3, 4, 5], [1, 2, 3, 1], [1, 2, 3, 2]]

Java代码
我不确定你能走多远以及它的表现如何。至少在我进行的少数测试中，它似乎工作得很好。您可能会找到更高效的解决方案，但我可以想象，这是解决此问题的一种方法。
无论如何，这是我的尝试:

public static void main(String args[]) {
    final List<Integer> list = Arrays.asList(1, 2, 3, 1, 3, 4, 3, 5, 1, 2, 1, 2, 2);
    final Map<Integer, Integer> occurrenceMap = findOccurrences(list);
    final Map<Integer, Integer> occurrenceMapSorted = occurrenceMap;
    occurrenceMapSorted.entrySet().stream()
        .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
        .forEach(System.out::println);
    
    final List<List<Integer>> sublists = setupSublists(list.size(), 3);
    System.out.println(sublists);
    
    final Map<Integer, Integer> usageMap = new HashMap<>(occurrenceMapSorted.size());
    
    for (int i = 0; i < sublists.size(); i++) {
        final List<Integer> sublist = sublists.get(i);
        populateSublist(occurrenceMapSorted, usageMap, sublist);
    }
    
    System.out.println(sublists);
}

public static void populateSublist(Map<Integer, Integer> occurrenceMapSorted, Map<Integer, Integer> usageMap, List<Integer> sublist) {
    int i = 0;
    int skipp = 0;
    while (i < sublist.size() && sublist.get(i) == 0) {
        for (Map.Entry<Integer, Integer> entry : occurrenceMapSorted.entrySet()) {
            if (skipp > 0) {
                skipp--;
                continue;
            }
            final int entryKey = entry.getKey();
            final Integer usageCount = usageMap.getOrDefault(entryKey, null);
            if (usageCount == null || usageCount < entry.getValue()) {
                if (usageCount == null) {
                    usageMap.put(entryKey, 1);
                } else {
                    usageMap.put(entryKey, usageCount + 1);
                }
                
                sublist.set(i, entryKey);
                System.out.println("i: " + i);
                System.out.println("sublist: " + sublist);
                
                System.out.println("usage: ");
                usageMap.entrySet().stream()
                    .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
                    .forEach(System.out::println);
                System.out.println();
                
                i++;
                skipp = i;
                break;
            }
        }
    }
}

public static List<List<Integer>> setupSublists(int listLength, int numberOfSublists) {
    if (numberOfSublists <= 1 || numberOfSublists > listLength) {
        throw new IllegalArgumentException("Number of sublists is greater than the number of elements in the list or the sublist count is less or equal to 1.");
    }
    final List<List<Integer>> result = new ArrayList<>(numberOfSublists);
    final int minElementCount = listLength / numberOfSublists;
    int remainder = listLength % numberOfSublists;
    for (int i = 0; i < numberOfSublists; i++) {
        final List<Integer> sublist = new ArrayList();
        boolean addRemainder = true;
        for (int j = 0; j < minElementCount; j++) {
            sublist.add(0);
            if (remainder > 0 && addRemainder) {
                sublist.add(0);
                addRemainder = false;
                remainder--;
            }
        }
        result.add(sublist);
    }
    return result;
}

public static Map<Integer, Integer> findOccurrences(List<Integer> list) {
    final Map<Integer, Integer> result = new HashMap();
    for (int i = 0; i < list.size(); i++) {
        final int listElement = list.get(i);
        final Integer entry = result.getOrDefault(listElement, null);
        if (entry == null) {
            result.put(listElement, 1);
        } else {
            result.put(listElement, entry.intValue() + 1);
        }
    }
    return result;
}