2

我有三个列表a，b，c。每个列表都包含许多按排序顺序排列的整数。

为了这个例子，让：

a = [2, 2, 7]
b = [4, 6, 9]
c = [3, 6, 8]

我的目标是按升序枚举三个列表中元素的所有可能产品。

最小的产品当然是a[0]*b[0]*c[0]. 在示例中，第二低的产品是a[0]*b[1]*c[0]。等等。

我正在尝试为任意数量的列表找到通用解决方案。我很难概括从第 k 个最低产品到 (k+1) 最低产品的步骤。

我不想列举所有可能的产品然后对它们进行排序，因为我正在处理可能非常多的列表，并且可能只对前 1000 个组合感兴趣。

任何帮助将不胜感激，包括教科书的指针。

4

1 回答 1

0

假设我们想要得到一个时间复杂度，O(N * K)其中N是列表的数量并且K是K-th 产品。我们在每个列表的开头维护一个指针（为简单起见，我将其称为P[i]- i'th 指针在 listi和L[i]- i'th 列表）。

最初P[i] = 0对于每个列表（因为我们从 0 开始索引列表）

Step 1: 第一个产品是L[0][P[1]] * L[1][P[2]] * .. L[N][P[N]]。

Step 2：对于下一步，我们有兴趣最小化下一个产品。我们选择j (0<=j<=N)最小L[j][P[j] + 1]的。我们递增P[j]，1然后继续Step 1计算下一个产品。我认为很明显，下一个产品应该是所有可能性中最小的。

如果您想计算唯一产品的数量，您只需维护一个计数器，仅当当前产品与以前的产品不同时才会增加该计数器。

您仍然可以O(log(N) * K)通过使用优先级队列来改进此算法，以便在Step 2.

于 2013-12-23T21:20:36.020 回答