[備忘]稀疏矩陣

說明

　　如果在矩陣中，多數的元素並沒有資料，稱此矩陣為稀疏矩陣（sparse matrix），由於矩陣在程式中常使用二維陣列表示，二維陣列的大小與使用的記憶體空間成正比，如果多數的元素沒有資料，則會造成記憶體空間的浪費，為此，必須設計稀疏矩陣的陣列儲存方式，利用較少的記憶體空間儲存完整的矩陣資訊。

　　陣列只儲存矩陣的行數、列數與有資料的索引位置及其值，在需要使用矩陣資料時，再透過程式運算加以還原，例如若矩陣資料如下 ，其中0表示矩陣中該位置沒有資料：

0 0 0 0 0 0
0 3 0 0 0 0
0 0 0 6 0 0
0 0 9 0 0 0
0 0 0 0 12 0

　　這個矩陣是5X6矩陣，非零元素有4個，使用的陣列第一列記錄其列數、行數與非零元素個數：

5 6 4

　　陣列的第二列起，記錄其位置的列索引、行索引與儲存值：

1 1 3
2 3 6
3 2 9
4 4 12

　　所以原本要用30個元素儲存的矩陣資訊，現在只使用了15個元素來儲存，節省了不少記憶體的使用。

Java程式碼

public class SparseMatrix {
   public static int[][] restore(int[][] sparse) {
       int row = sparse[0][0];
       int column = sparse[0][1];
      
       int[][] array = new int[row][column];
      
       int k = 1;
       for(int i = 0; i < row; i++) {
           for(int j = 0; j < column; j++) {
               if(k <= sparse[0][2] &&
                   i == sparse[k][0] &amp;& j == sparse[k][1]) {
                   array[i][j] = sparse[k][2];
                   k++;
               }
               else
                   array[i][j] = 0;
           } 
       }
      
       return array;
   }

   public static void main(String[] args) {
       int[][] sparse = {{5, 6, 4},
                         {1, 1, 3},
                         {2, 3, 6},
                         {3, 2, 9},
                         {4, 4, 12}};
      
       int[][] array = SparseMatrix.restore(sparse);
      
       for(int i = 0; i < array.length; i++) {
           for(int j = 0; j < array[i].length; j++) {
               System.out.print(array[i][j] + " ");
           } 
           System.out.println();
       }
   }
}