1、稀疏陣列-有解無憂

來源：https://www.bilibili.com/video/BV1B4411H76f?p=9

一、稀疏陣列的基本介紹

　　一個二維陣列中，如果大部分元素為0，或者是同一個值，可以用一種更簡單的方式存盤該陣列，

　　1）記錄二維陣列有幾行幾列，一共有多少個值；

　　2）記錄這些值所在的位置及值的大小，

　　這樣形成的陣列就是稀疏陣列，

二、稀疏陣列實體

　　1、原始的二維陣列

 1 0    0    0    0    0    0    0    0    0    0    0    
 2 0    0    1    0    0    0    0    0    0    0    0    
 3 0    0    0    2    0    0    0    0    0    0    0    
 4 0    0    0    0    0    0    0    0    0    0    0    
 5 0    0    0    0    0    0    0    0    0    0    0    
 6 0    0    0    0    0    0    0    0    0    0    0    
 7 0    0    0    0    0    0    0    0    0    0    0    
 8 0    0    0    0    0    0    0    0    0    0    0    
 9 0    0    0    0    0    0    0    0    0    0    0    
10 0    0    0    0    0    0    0    0    0    0    0    
11 0    0    0    0    0    0    0    0    0    0    0

　　2、對應的稀疏陣列

1 11   11   2    
2 1    2    1    
3 2    3    2

　　稀疏陣列中：

　　　　第一行[11,11,2]表示原二維陣列有11行11列2個值；

　　　　第二行[1,2,1]表示下標為(1,2)的位置有一個值，值為1；

　　　　同理，第三行[2,3,2]表示下標為(2,3)的位置有一個值，值為2，

三、應用實體

　　1、問題描述

　　1）把上述二維陣列存為稀疏陣列

　　2）將存盤后的稀疏陣列恢復為原始陣列

　　2、思路

　　1）二維陣列→稀疏陣列

　　　　• 遍歷原始陣列得到有效資料的個數sum;

　　　　• 根據sum創建稀疏陣列spareArr [sum+1][3];

　　　　• 將有效資料存盤到稀疏陣列，

　　2）稀疏陣列→二維陣列

　　　　• 讀取稀疏陣列第一行，創建原始二維陣列;

　　　　• 讀取稀疏陣列后面的行，賦值給二維陣列對應的位置，

　　3、代碼實作

　　1）創建二維陣列

 1 // 創建原始二維陣列 11*11
 2 int chessArr1[][] = new int[11][11];
 3 chessArr1[1][2] = 1;
 4 chessArr1[2][3] = 2;
 5 //輸出原始陣列
 6 for(int[] row : chessArr1) {
 7     for(int data : row) {
 8         System.out.printf("%d\t",data);
 9     }
10     System.out.println();
11 }

　　2）二維陣列→稀疏陣列

 1 //*************************將二維 轉 稀疏
 2 //遍歷得到非零資料個數
 3 int sum = 0;
 4 for(int i = 0;i < 11; i++) {
 5     for(int j = 0;j < 11; j++) {
 6     if(chessArr1[i][j] != 0) {
 7         sum++;
 8     }
 9     }            
10 }
11         
12 //創建稀疏
13 int sparseArr[][] = new int[sum+1][3];
14 sparseArr[0][0] = 11;
15 sparseArr[0][1] = 11;
16 sparseArr[0][2] = sum;
17         
18 //稀疏賦值
19 int count = 0;//記錄是第幾個非零資料
20 for(int i = 0;i < 11; i++) {
21     for(int j = 0;j < 11; j++) {
22         if(chessArr1[i][j] != 0) {
23             count++;
24             sparseArr[count][0] = i;
25             sparseArr[count][1] = j;
26             sparseArr[count][2] = chessArr1[i][j];
27         }
28     }            
29 }
30         
31 //輸出
32 System.out.println();
33 System.out.println("得到的稀疏陣列為:");
34 for(int i = 0; i < sparseArr.length; i++) {
35     System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
36 }
37 System.out.println();

　　3）稀疏陣列→二維陣列

//***********************稀疏恢復
int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
for(int i = 1;i < sparseArr.length; i++) {
    chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
                        
}
        
//輸出
System.out.println();
System.out.println("恢復的二維陣列為:");
for(int[] row : chessArr2) {
    for(int data : row) {
        System.out.printf("%d\t",data);
    }
    System.out.println();
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/51508.html

標籤：其他

上一篇：變分深度嵌入(Variational Deep Embedding, VaDE)

下一篇：論文翻譯：《PRIMES is in P》——素性測驗的確定性多項式時間演算法研究