java - 矩阵操作 : logic not fetching correct answer for higher order NXN matrix data

Question

我遇到了以下与矩阵操作相关的问题。

问题陈述

有一个NxN矩阵，分为N * N个单元格。每个单元格都有一个预定义的值。这将作为输入给出。迭代必须发生 K 次，这也在测试输入中给出。我们必须确保在每次迭代中选择行/列的最佳/最小值。最终输出为每次迭代结束时保存的最优值的累加和。

步骤 1. 对单个行和列求和，求行和列的最小和，(可以是行也可以是列，只需要最小的行或列)

第2步。分别存储上面找到的总和

第 3 步。最小的增量元素。求和行或列。 1

从 1 到第 K 个值重复步骤 1、2、3

add the sum at each iteration(specified in step2)

输出是第K次迭代得到的和。

示例数据

2 4
1 3
2 4

输出数据

22

我能够编写代码(在 Java 中)并针对一些示例测试用例测试相同的代码。输出工作正常。该代码适用于较低阶的样本数据矩阵，例如 2x2、4x4，甚至直到 44x40(迭代次数较少)。但是，当矩阵大小增加到 100X100(复杂迭代)时，我看到预期输出输出值与实际输出及其随机数在 10s 和百位不同。因为我无法找到正确的输出与输入模式。现在，真正调试第 500 个循环以确定问题对我来说是一个损失。有没有更好的方法或方法来解决与巨大矩阵操作相关的此类问题。有没有人遇到过类似的问题并解决了。

我主要想了解解决给定矩阵问题的正确方法。 java中使用什么数据结构。目前，我正在使用原始 DS 和数组 int[] 或 long[] 来解决这个问题。感谢这方面的任何帮助。

Answer 1

哪个数据结构？

您在这里需要的是一种数据结构，它允许您高效查询和更新最小总和行。最常用的是堆 https://en.wikipedia.org/wiki/Heap_(data_structure) .

为了您的目的，最好只实现最简单的一种，即基于数组的二进制堆:

• 请参阅此处:https://en.wikipedia.org/wiki/Binary_heap
• 在这里:http://courses.cs.washington.edu/courses/cse373/11wi/homework/5/BinaryHeap.java

..实现细节。

---

程序:

• 将堆初始化为大小 M + N其中 M, N是行数和列数。
• 在循环之前，预先计算每一行和每一列的总和，并将它们作为对象添加到堆中。同时添加两个数组 A, B分别存储行和列对象。
• 现在堆化关于行总和属性的堆数组。这确保堆遵循二叉堆结构的标准(父总是 > 子)。阅读源代码以了解有关如何实现此功能的更多信息(对于固定数组来说非常容易)
• 对于每次迭代，查看堆数组中的第一个 元素。这始终是行总和最小的那个。如果这是一个行对象，则将 sum 属性递增 N (列数)，并递增 B 中的每个对象(列列表)乘以 1。如果它是一列，则执行相同的操作。
• 在此之后，总是在下一次迭代之前heapify。

最后，只返回第一个元素的属性。

---

时间复杂度:

原始的朴素解决方案(每次循环遍历所有列和行)是 .

使用堆，每一步的heapify操作都是 (对于二进制堆)。

这意味着总复杂度为 , FAR 更小。 max术语是为了补偿这样一个事实，即在每次迭代中，它可能是行 或 列递增。

---

作为旁注，还有其他堆结构类型的时间复杂度甚至比二叉堆更好，例如二叉树、斐波那契堆等。然而，这些要复杂得多，因此具有更高的常数因子开销。因此，对于您的项目，我觉得它们不是必需的，因为它们中的许多都需要惊人的数据集大小来证明常数因子开销的合理性。

此外，它们都支持与二叉堆相同的外部操作，正如堆的抽象数据结构定义。

(heapify 是二叉堆结构特有的内部操作。其他一些在理论上更优越，因为它们隐式地和“懒惰地”执行此操作)