有時(shí)候使用二維數(shù)組來(lái)保存數(shù)據(jù)的時(shí)候荡澎，會(huì)出現(xiàn)這種情況：
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
3 0 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 7
我們看見(jiàn)這種情況的數(shù)組有很多的相似的數(shù)據(jù)柜与。在這50個(gè)數(shù)據(jù)中笙以，除了其中的4的數(shù)據(jù)外（后面我們把這4個(gè)數(shù)字比喻做特殊數(shù)字）日麸，其他的全部都是0漠嵌。
如果我們直接用二維數(shù)組來(lái)保存這些數(shù)據(jù)的話哼拔，就會(huì)花費(fèi)很多的內(nèi)存嚼黔。所以我們需要用一種方式來(lái)將這個(gè)數(shù)組進(jìn)行化簡(jiǎn)之后存儲(chǔ)细层。
我們先來(lái)看一下化簡(jiǎn)之后的(稀疏)數(shù)組是什么樣子：
5 ???????10 ???????4
1 ????????5???????? 1
2 ????????0???????? 3
3 ????????3 ????????2
4 ????????9 ????????7
經(jīng)過(guò)化簡(jiǎn)之后，就從5 × 10 的數(shù)組變成了5 × 3的數(shù)組唬涧。要存儲(chǔ)的數(shù)據(jù)也變成了15個(gè)疫赎。這大大減少了存放數(shù)據(jù)所占用的空間。
現(xiàn)在我們來(lái)解釋一下轉(zhuǎn)換后的數(shù)組每行每列的意義：
在轉(zhuǎn)換后的第一行中碎节，
5 ???????10 ???????4
這三個(gè)數(shù)捧搞，5代表原數(shù)組有5行，10代表原數(shù)組有10列狮荔，4則代表有4個(gè)數(shù)（因?yàn)槠渌臄?shù)字都是0胎撇，而這4個(gè)數(shù)都是不同與0的需要存儲(chǔ)的數(shù)字）。這個(gè)4也同時(shí)定義了稀疏數(shù)組的大小殖氏。
稀疏數(shù)組的列是固定的晚树，即col = 3，而行則是需要存放數(shù)字個(gè)數(shù)加一（算上存放原數(shù)組的信息）雅采。拿這個(gè)例子來(lái)說(shuō)爵憎，稀疏數(shù)組的大小應(yīng)該是 sparseArray[5][3]而在接下來(lái)的4行內(nèi)容的性質(zhì)都是一樣的：需要存儲(chǔ)的原數(shù)組中特殊信息。
例如這個(gè)第二行
1 ????????5???????? 1
1代表是這個(gè)特殊數(shù)字在整個(gè)數(shù)組的第1行婚瓜，5代表是在第5列宝鼓，1就是這個(gè)位置存放的那個(gè)數(shù)字。
類(lèi)似這樣以此往后闰渔。
接下來(lái)用代碼來(lái)進(jìn)行實(shí)現(xiàn)這個(gè)稀疏數(shù)組：
- 首先我們創(chuàng)建一個(gè)二維數(shù)組
int[][] Array = new int[5][10];
Array[1][5] = 1;
Array[2][0] = 3;
Array[3][3] = 2;
Array[4][9] = 7;
- 然后需要對(duì)這個(gè)數(shù)組進(jìn)行遍歷席函，數(shù)出有多少個(gè)特殊數(shù)字
int sum = 0;
for (int i = 0; i < Array.length; i++) {
for (int j = 0; j < Array[0].length; j++) {
if (Array[i][j] != 0)
sum ++;
}
}
- 當(dāng)我們知道了有多少個(gè)特殊數(shù)字之后，就可以創(chuàng)建稀疏數(shù)組了
int[][] sparseArray = new int[sum + 1][3];
sparseArray[0][0] = Array.length;
sparseArray[0][1] = Array[0].length;
sparseArray[0][2] = sum;
int count = 0;
for (int i = 0; i < Array.length; i++) {
for (int j = 0; j < Array[0].length; j++) {
if (Array[i][j] != 0){
count ++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = Array[i][j];
}
}
}
- 然后我們可以將該數(shù)組輸出看看結(jié)果如何
for (int i = 0; i < sparseArray.length; i++) {
for (int j = 0; j < sparseArray[i].length; j++) {
System.out.printf("%d\t", sparseArray[i][j]);
}
System.out.println();
}
除了將二維數(shù)組轉(zhuǎn)化為稀疏數(shù)組之外冈涧，我們也需要在使用數(shù)組時(shí)把稀疏數(shù)組轉(zhuǎn)化為二維數(shù)組：
- 首先獲取稀疏數(shù)組第一行的信息來(lái)創(chuàng)建二維數(shù)組：
int[][] sourceArray = new int[sparseArray[0][0]][sparseArray[0][1]];
- 然后將稀疏數(shù)組中的數(shù)據(jù)存放到創(chuàng)建的這個(gè)原數(shù)組中：
for (int i = 1; i < sparseArray.length; i++) {
sourceArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
