我有三个列表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种组合感兴趣。
假设我们想要得到O(N * K)的时间复杂度，其中N是列表的数量，K是K的第六个乘积。我们在每个列表的开头都保留一个指针（为了简单起见，我将此指针称为列表i的第P[i]-i个指针，L[i]-第i个列表）。
最初，每个列表的P[i] = 0（因为我们从0开始索引列表）
Step 1：第一个产品是L[0][P[1]] * L[1][P[2]] * .. L[N][P[N]]。
Step 2：下一步我们有兴趣尽量减少下一个产品。我们选择L[j][P[j] + 1]最小的j (0<=j<=N)。我们将P[j]增加1，然后在Step 1处计算下一个乘积。我认为很明显，下一个产品应该是所有可能性中最小的。
如果您想计算唯一产品的数量，只需维护一个计数器，只有当当前产品与以前的产品不同时，该计数器才会递增。
您仍然可以通过使用优先级队列将该算法改进为O(log(N) * K)，以便在Step 2处获得最小值。