矩阵操作：逻辑无法获取更高阶NXN矩阵数据的正确答案

我遇到了与Matrix Manipulation相关的问题。

问题陈述

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

步骤1.总结单个行和列，找到行和列的最小总和（它可以是行或列，只需要最小行或列）

步骤2.分别存储上面找到的总和

第3步。增加min的元素。 总和行或列。 由1

从1到Kth值重复步骤1,2,3

add the sum at each iteration(specified in step2) 

输出是在第K次迭代上获得的总和。

样本数据

 2 4 1 3 2 4 

输出数据

22

我能够编写一个代码（在java中）并对一些示例测试用例进行了相同的测试。 输出工作正常。 该代码适用于较低阶的样本数据矩阵，例如2×2,4×4，甚至直到44×40（迭代次数较少）。 但是，当矩阵大小增加到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 ，它们分别存储行和columon对象。
• 现在，根据行sum属性堆积堆数组。 这可确保堆遵循二进制堆结构的标准（父总是>子项）。 阅读源代码以了解有关如何实现此更多信息（对于固定数组非常容易）
• 对于每次迭代，请查看堆数组中的第一个元素。 这总是具有最小线总和的那个。 如果这是一个行对象，则将sum属性递增N （列数），并将B每个对象（列列表）递增1.如果它是列，则执行相同操作。
• 在此之后，始终在下一次迭代之前堆积 。

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

---

时间复杂度 ：

原始的天真解决方案（每次遍历所有列和行）是 。

使用堆，每步的heapify操作是 （对于二进制堆）。

这意味着总的复杂性 ， FAR更小。 max项是为了补偿在每次迭代时它可以是递增的行或列的事实。

---

作为旁注，还有其他堆结构类型比二进制堆具有更好的时间复杂度，例如二项式树，Fibonacci堆等。然而，这些更复杂，并且因此具有更高的恒定因子开销。 因此，对于您的项目，我觉得它们不是必需的，因为它们中的许多都需要非凡的数据集大小来certificate恒定的因子开销。

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

（heapify是一个特定于二进制堆结构的内部操作。相当多的其他一些在理论上是优越的，因为它们隐式地执行此操作并且“懒惰地”）

Answer 2

O（KN + N * N）解决方案：
您可以使用列和行的总和，而不是直接存储或操作它们。

---

首先对所有列和行求和，在2 * N数组中，第一行是列的总和， a[0][0]是第一列的总和， a[0][1]是第二列的总和，第二行row是行的总和，第一行a[1][0]和等等…

---

然后执行以下迭代：

1. 在数组a中找到min。
2. 将其添加到答案中。
3. 将N添加到所选行或列的最小值。
4. 如果min是row，则在所有cols中添加一个cols，如果是列，则在所有cols中添加一个。 如果需要任何进一步的解释，请不要犹豫，发表评论。

Answer 3

我这样做是为了解决上述问题……

  void matrixManipulation() throws IOException { int N = Reader.nextInt(); int[][] matrix = new int[N][N]; int K = Reader.nextInt(); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { matrix[i][j] = Reader.nextInt(); } } // System.out.println("********Inital position**********"); // for (int i = 0; i < N; i++) { // for (int j = 0; j < N; j++) { // System.out.print(matrix[i][j]); // } // System.out.println(); // } // System.out.println("********Inital position**********"); CalculateSum calculateSum = new CalculateSum(); int[] row = new int[N]; int[] row_clone = new int[N]; int[] col = new int[N]; int[] col_clone = new int[N]; int test =0; for (int kk = 0; kk < K; kk++) { row = calculateSum.calculateRowSum(matrix, N); row_clone = row.clone(); /* just sort it either Arrarys sort or any other ---starts here*/ // for (int i = 1; i < row.length; i++) { // row_orignial[i] = row[i]; // } // Arrays.sort(row); Node root1 = insert(null, row[0], 0, row.length); for (int i = 1; i < row.length; i++) { insert(root1, row[i], 0, row.length); } sortArrayInOrderTrvsl(root1, row, 0); /* just sort it either Arrarys sort or any other ---ends here*/ col = calculateSum.calculateColumnSum(matrix, N); col_clone = col.clone(); /* just sort it either Arrarys sort or any other ---starts here*/ // for (int i = 1; i < col.length; i++) { // col_orignial[i] = col[i]; // } // Arrays.sort(col); Node root2 = insert(null, col[0], 0, col.length); for (int i = 1; i < row.length; i++) { insert(root2, col[i], 0, col.length); } sortArrayInOrderTrvsl(root2, col, 0); /* just sort it either Arrary.sort or any other---ends here */ int pick = 0; boolean rowflag = false; int rowNumber = 0; int colNumber = 0; if (row[0] < col[0]) { pick = row[0];// value rowflag = true; for (int i = 0; i < N; i++) { if (pick == row_clone[i]) rowNumber = i; } } else if (row[0] > col[0]) { pick = col[0];// value rowflag = false; for (int i = 0; i < N; i++) { if (pick == col_clone[i]) colNumber = i; } } else if(row[0] == col[0]){ pick = col[0]; rowflag = false; for (int i = 0; i < N; i++) { if (pick == col_clone[i]) colNumber = i; } } test= test + pick; if (rowflag) { matrix = rowUpdate(matrix, N, rowNumber); } else { matrix = columnUpdate(matrix, N, colNumber); } System.out.println(test); // System.out.println("********Update Count"+kk+" position**********"); // for (int i = 0; i < N; i++) { // for (int j = 0; j < N; j++) { // System.out.print(matrix[i][j]); // }System.out.println(); // } // System.out.println("********Update Count"+kk+" position**********"); } // System.out.println("********Final position**********"); // for (int i = 0; i < N; i++) { // for (int j = 0; j < N; j++) { // System.out.print(matrix[i][j]); // }System.out.println(); // } // System.out.println("********Final position**********"); // System.out.println(test); }