vpodlesnyak
BAN USERThis solution requires (N-1)*N/2 place for storage and seek time is constant
- vpodlesnyak January 15, 2013I suggest following solution (written in java):
public static void main(String[] args) {
int N = 5;
int[][] matrix = new int[][]{
{ 0, 1, 2, 3, 4},
{ 1, 0, 5, 6, 7},
{ 2, 5, 0, 8, 9},
{ 3, 6, 8, 0,10},
{ 4, 7, 9,10, 0},
};
int[] matrixArray = new int[]{
1, 2, 3, 4,
5, 6, 7,
8, 9,
10
};
// print to ensure that representation is ok
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(getMatrixElement(matrixArray, i, j, N)+" ");
}
System.out.println();
}
}
static int getMatrixElement(int[] matrixArray, int i, int j, int N) {
//check index validity
if (i < 0 || N <= i || j < 0 || N <= j) throw new IllegalArgumentException();
//check equality
if (i == j) return 0;
// ensure j<i
if (i < j) {
int tmp = i;
i = j;
j = tmp;
}
int rowOffset;
if (j == 0){
rowOffset = 0;
} else {
rowOffset = (2*N-j-1) * j/2; // offset is an arithmetic progression like: 4 .. 3 .. 2 .. 1
}
return matrixArray[rowOffset + (i-j-1)];
}
Sorry, I just figured out that this is the same SRB wrote
- vpodlesnyak January 16, 2013