用Java表示上三角矩阵的最佳数据结构是什么？

Question

假设给出了一个整数上三角矩阵。用Java存储这个最好的方法是什么？天真的2d int数组显然不高效。我提出的解决方案转移到答案部分。

Answer 1

我想我找到了解决方案。这里是我的解决方案：假设你有一个4X4的上三角矩阵M.

1 2 3 4 
0 6 7 1 
0 0 8 9 
0 0 0 5 

如果你能在一维数组M的每一个元素映射，这是最好的解决方案。所有你需要知道的是知道矩阵的哪个[行，列]对应于你的1d数组中的哪一个元素。这里是你怎么做的魔力：

start_index=((col_index-1)+1)+((col_index-2)+1)+...+1 
end_index=start_index + col_index 

例如：如果我想找到在哪里都在矩阵的第三列的元素，在数组中：

start_index=((3-1)+1)+((3-2)+1)+((3-3)+1)=6 
end_index=6+3=9 

因此，所有我需要做的是从我的数组的索引6开始，读取所有元素直到索引9（包括第9个元素）。按照这个过程，你可以在（n + n^2）/ 2空间中存储和检索nXn矩阵的所有单元。

Answer 2

如果矩阵始终是对角线，我会用：

List<List<Integer>> matrix = ... 

如果它是一个稀疏矩阵，我会使用地图：

Map<Map<Integer>> = ... 

在第二种情况下，您可能需要使用get和set操作将该映射包装到类中，以便管理对新行和列的访问。

所有这些都取决于您的需求，您的记忆限制和矩阵大小。

Answer 3

番石榴的Table呢？它是使用HashMaps或TreeMaps（以及需要的2D数组）实现的，但它提供了比定义Map<Integer, Map<Integer, V>>更好的API。

Answer 4

如果你想节省内存，你的解决方案看起来不错 - 它被称为packed storage matrix。逐列，自上而下，你的阵列应该是这样的：1 2 6 3 7 8 4 1 9 5

我建议你指数的一个简单的计算，基于和公式(n² + n)/2（行和列是从零开始）。

list_index = (column^2 + column)/2 + row; 

实现可能如下所示：

public class TriangularMatrix { 
    private final int[] list; 

    public TriangularMatrix(int size) { 
     list = new int[sumFormula(size)]; 
    } 

    public int set(int row, int column, int value) { 
     validateArguments(row, column); 

     int listIndex = getListIndex(row, column); 
     int oldValue = list[listIndex]; 
     list[listIndex] = value; 

     return oldValue; 
    } 

    public int get(int row, int column) { 
     validateArguments(row, column); 

     return list[getListIndex(row, column)]; 
    } 

    private void validateArguments(int row, int column) { 
     if (row > column) { 
      throw new IllegalArgumentException("Row (" + row + " given) has to be smaller or equal than column (" + column + " given)!"); 
     } 
    } 

    private int getListIndex(int row, int column) { 
     return sumFormula(column) + row; 
    } 

    private int sumFormula(int i) { 
     return (i*i + i)/2; 
    } 
} 

有another question on SO讨论（负）的性能影响，虽然它的Fortran。