最小化二维数组中列的数组样本总和，并限制所使用的行数

Question

如果我有一个 (N, M) 形状的二维数组。 我想找到沿 N 轴的最小值的最小总和。 但我对可以使用多少行（M 轴）进行值选择有限制，让这个值作为 L。

对于像这样的数组。

[[  8   7   7   7   7   7   7   5   6]
 [  5   7   6   5   6   6   7   7   5]
 [  7   8   8   8   5   5   5   6   7]
 [  7   8   7   7   7   6   7   8   5]
 [  0   0 100 100 100 100 100 100 100]
 [100 100 100   0   0 100 100 100 100]
 [100 100 100 100 100 100   0   0 100]]

我将选择第 1、4、5、6 行。

我正在为这个问题撞墙。而且我无法让 ChatGPT 来解决它。

我有一个强力解决方案是找到所有组合 C(N, C)。 对于每个组合数组，我找到沿 N 的最小值并迭代所有组合。

还有什么更好的办法吗？因为 N 和 M 可能相当大。

Answer 1

恕我直言，您还没有用足够的细节和示例输入和输出来定义问题来确定您的问题。但据我了解，您需要

L

行中的

M

最小值，其中

L <= M

。

M

中的每一行都有

N

种可能性。

如果我对问题的理解是正确的，则在您的示例中为

L = 4

，而必须选择行

4,5,6

，因为它们都有一个

0

，剩余的一行可以是任何其他剩余行，并且不需要是行

1

，因为所有其他行的最小值都是

5

。

如果我的假设是正确的，那么你能做的最好的就是使用

O(N * M) + O(N * log L)

时间复杂度和

O(L)

空间复杂度算法。

理由如下：

• 您需要找到每一行中的最小值，因此您必须查看矩阵中的每个值，因为数据没有其他约束、顺序等。这会给你

  O(N * M)

  。
• 您需要选择具有最小值的

  L

  行。这会给你

  O(N * log L)

  。

算法的工作原理如下：

1. 初始化最大堆大小为

   L

   、

   hp

   。
2. 循环一行的值并跟踪最小值。空间恒定，列数 (M) 的线性时间。
3. 将行的最小值添加到最大堆中。所选行数 (L) 的对数时间复杂度。
4. 如果最大堆中的元素数量大于

   L

   ，则从最大堆中弹出一个元素。对数时间复杂度 (L)。
5. 转到步骤

   2

   并重复下一行。行数 (N) 呈线性。
6. 最后，对最大堆中的元素求和。使用正确的数据结构，可以在线性时间 (L) 内完成，否则需要线性时间 (L * log L)。

希望有帮助！