如何将一个数组划分成K个子数组，使得所有子数组中重复元素数量的总和最小？

Question

作为示例，假设数组为A={1,1,2,1,2}且K=3。A可以分成{1}，{1,2}和{1,2}。所以，在这些子数组中重复元素的数量为0、0和0。因此，它们的总和为0。

- Atul Kumar Ashish

---

这不是一个作业问题。实际问题是不同的。如果我知道这个作为子问题的解决方法，我已经考虑过解决实际问题了。所以，所问的问题是解决实际问题的中间思路。 - Atul Kumar Ashish

Answer 1

这是一个非常有趣的挑战。我使用Java来说明我的方法。

将问题分解为小块
我将整个问题分成了更小的部分：

1. 我们需要根据拆分大小设置子数组的存储
2. 子数组应包含相同数量的元素，除非有余数（例如，10个元素分成k = 3个子数组，结果为长度为：3、3、4）
3. 以最少的重复方式将元素拆分到子数组中

1 + 2 - 将数组分成相等的部分
我已经用长度为10的数组和k = 3做了例子。由于除法给出的余数，子数组将是长度为3、3和4。

在代码片段中，我确保用0填充数组，并且每个子数组将有0到1个额外元素。如果有余数，额外的元素将分配到所有子数组中。

在我的例子中，我使用了一个长度为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，因此想法是将所有出现的次数平均分配到所有子数组中。如果我们最终得到像4x 1和4x 2以及k = 3（如上面的示例），那么我们可以将一个1和2放入每个子数组中。这使我们每个都有一个重复项（一个额外的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;
}

- F. Müller

Answer 2

让dp[i][k]表示到第i个索引的最佳分割为子数组。如果A[i]不出现在我们刚选择的最后一个子数组中，那么如果我们添加它，最优解不会改变。否则，我们的选择是开始一个新的子数组或缩短先前选择的子数组，直到它通过其中包含的A[i]的最左出现位置并查看是否更好。

如果我们进一步扩展它；首先，我们通过添加A[i]已经将最优解增加了1；如果我们有一个先前的可能性（最多A [ i-1] [k]）小于1（因此补偿添加），我们会从中开始。

为了计算新的可能性，其中当前第k个子数组的左边界刚好位于A[i]最左出现的右侧，我们可以在O(log n)内找到建议的k个子数组和建议的(k-1)个子数组中不同值的数量（波束树是一种选择），并从每个总元素数中减去这些计数。

- גלעד ברקן