arrays - n 个数组的最小 "n"和

Question

几年前，我试图做我 friend 的问题集，以提高我对数据结构等方面的知识。我遇到了这个问题，但我不确定从哪里开始。希望有人能帮助我!

给定 n 个未排序的数组，每个数组有 n 个元素。例如。

3 1 2
7 6 9
4 9 12

现在，假设我们从每个数组中取出一个元素，并将它们相加。让我们将这些元素的总和称为“n-sum”。

我需要设计一种算法，为我们提供 n 个最小的“n 和”(允许重复)。

在我们上面的例子中，答案是:

11, 12, 12

# 11 comes from: 1 (first array) + 6 (second array) + 4 (third array)
# 12 comes from: 2 (first array) + 6 (second array) + 4 (third array)
# 12 comes from: 1 (first array) + 7 (second array) + 4 (third array)

其中一个建议是使用优先级队列。

谢谢!

Answer 1

时间至少是O(n^2):你必须访问所有数组元素，因为如果所有元素都等于1000除了每行中的on为0，你将不得不查看n个元素等于0 ，或者您找不到最小的总和。

对每一行进行排序，执行 O (n^2 log n) 步。在每一行中，将该行的所有元素减去第一个元素，所以每一行的第一个元素为0；在找到最小的金额后，您可以对其进行补偿。你的例子变成了

3 1 2  -> 1 2 3 -> 0 1 2
7 6 9  -> 6 7 9 -> 0 1 3
4 9 12 -> 4 9 12-> 0 5 7

现在如果有 m 个和，则可以分 m 步找到所有 ≤ K 的和:在第一行中，依次选择所有值，只要它们≤ K。在第二行中，依次选择所有值作为只要两行的总和≤ K，依此类推。由于每一行都从 0 开始，因此不会浪费时间。

例如，总和≤5是:0+0+0, 0+0+5, 0+1+0, 0+3+0, 1+0+0, 1+1+0, 1+3 +0、2+0+0、2+1+0、2+3+0。比我们需要的三个多得多。如果我们在找到 3 个和 ≤ 5 后停止，我们很快就会知道“至少有 3 个和 ≤ 5”。我们需要提前停止，因为在一般情况下可能有 n^n 种可能的和。

如果您选择 K =“第二列中的最大元素”，那么您知道至少有 n+1 个总和的值≤ K，因为您可以从第二列中选择全 0 或除一个值外的全 0柱子。在您的示例中，K = 5(我们知道它有效)。设 X 为 n 个和≤X 但少于 n 个和≤X - 1 的值。我们在 0 和 K 之间用二分查找找到 X，然后找到和。示例:

已知 K = 5 足够大。我们尝试 K = 2，并找到 4 个和(实际上我们停在 3 个和)。太多。我们试K=1，有0+0+0、0+1+0、1+0+0三种解。我们尝试 K = 0，但只有一种解决方案。

这部分进行得很快，所以我们会尽量减少用于排序的时间。我们注意到，在这种情况下，查看前两列就足够了。我们可以在每一行中找到两个最小的项目，在这种情况下就足够了。如果两个最小的项目不足以确定 n 个最小的和，请在需要的地方找到第三个最小的项目等。例如，由于最后一行的第二大项是 5，我们不需要该行的第三项，因为如果 K ≤ 4，即使 5 也不是和的元素。