-
簡(jiǎn)介
關(guān)于對(duì)稱矩陣的性質(zhì)請(qǐng)參考SymmetricMatrix
對(duì)稱矩陣
對(duì)于對(duì)稱矩陣我們可以使用一個(gè)一維數(shù)組來(lái)進(jìn)行壓縮存儲(chǔ)圈纺，每一個(gè)位置存儲(chǔ)一對(duì)矩陣元。
對(duì)于N階矩陣所使用的的存儲(chǔ)空間為1+2+3+……+n = n * (n+1)/2;
我們將對(duì)稱矩陣當(dāng)做一個(gè)二維空間來(lái)思考,每一個(gè)元對(duì)應(yīng)x,y軸上的一點(diǎn)。而對(duì)應(yīng)的a(0,0)元素在坐標(biāo)(1,1)的位置。
假設(shè)元a位于坐標(biāo)(x,y)。那么此時(shí)對(duì)應(yīng)壓縮后的一維數(shù)組的坐標(biāo)為y軸以上的三角區(qū)域的元數(shù)量[(y-1) * y / 2],加上x(chóng)軸的偏移位置攒驰。也即是Array[y * (y+1) / 2 + x] = A[x][y];
-
代碼實(shí)現(xiàn)
@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++) {
//根據(jù)性質(zhì)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();
}
}
