-
简介
关于对称矩阵的性质请参考SymmetricMatrix
对称矩阵
对于对称矩阵我们可以使用一个一维数组来进行压缩存储，每一个位置存储一对矩阵元。
对于N阶矩阵所使用的的存储空间为1+2+3+……+n = n * (n+1)/2;
我们将对称矩阵当做一个二维空间来思考,每一个元对应x,y轴上的一点。而对应的a(0,0)元素在坐标(1,1)的位置。
假设元a位于坐标(x,y)。那么此时对应压缩后的一维数组的坐标为y轴以上的三角区域的元数量[(y-1) * y / 2],加上x轴的偏移位置。也即是Array[y * (y+1) / 2 + x] = A[x][y];
-
代码实现
@Test
public void symmetricCompression() {
int[][] symmetricMatrix = {
{1, 2, 3, 4, 5},
{2, 1, 2, 3, 4},
{3, 2, 1, 2, 3},
{4, 3, 2, 1, 2},
{5, 4, 3, 2, 1}
};
int[] result = compression(symmetricMatrix);
for (int i : result) {
System.out.print(i + "\t");
}
System.out.println();
printCompression(result);
}
private int[] compression(int[][] target) {
int[] result = new int[target.length * (target.length + 1) >> 1];
int i = 0;
for (int y = 0; y < target.length; y++) {
for (int x = 0; x <= y; x++) {
result[i++] = target[y][x];
}
}
return result;
}
private void printCompression(int[] result) {
//解一元二次方程
int N = (-1 + (int) Math.sqrt(1 + (4 * (result.length << 1)))) >> 1;
int location;
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
//根据性质a(i,j) = a(j,i)得到
if (x <= y) {
location = ((y * (y + 1)) >> 1) + x;
} else {
location = ((x * (x + 1)) >> 1) + y;
}
System.out.print(result[location] + "\t");
}
System.out.println();
}
}
