Suppose an upper triangular matrix of integers is given. What's the best way of storing this in Java? The naive 2d int array is obviously not efficient. The solution I came up with was moved to the answers section.
I think I found the solution. Here is my solution: Assume you have a 4X4 upper triangular matrix M.
1 2 3 4
0 6 7 1
0 0 8 9
0 0 0 5
If you can map every element of M in a 1d array, that's the best solution. All you need to know is to know which [row,col] of matrix corresponds to which element of your 1d array. Here is how you do the magic:
start_index=((col_index-1)+1)+((col_index-2)+1)+...+1
end_index=start_index + col_index
For example: if I want to find where are the elements on the 3rd column of the matrix, in the array:
start_index=((3-1)+1)+((3-2)+1)+((3-3)+1)=6
end_index=6+3=9
So, all I need to do is to start at index 6 of my array, and read all the elements till index 9 (including 9th element). Following this procedure, then you can store and retrieve all the cells of the nXn matrix in (n + n^2)/2 space.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments