数组转稀疏数组
- 遍历原始数组，找出有效数据个数
n；
- 根据有效数据个数，构建稀疏数组
sparseArr = int[n+1][3];
- 将原始数组的行数
row、列数column和有效数据个数n填入稀疏数组的第一行 sparseArr[0] =new int[] {row, column, n};
- 遍历原始二维数组，找到有效数据依次填入稀疏数组；
public static int[][] toSparse(int[][] arr, int exclude) {
int row = arr.length;
int column = arr[0].length;
int n = 0;
for(int i = 0; i < row; i++) {
for(int j = 0; j < column; j++) {
if(arr[i][j] != exclude) {
n += 1;
}
}
}
int[][] sparseArr = new int[n+1][3];
sparseArr[0] = new int[]{row, column, n};
int t = 1;
for(int i = 0; i < row; i++) {
for(int j = 0; j < column; j++) {
if(arr[i][j] != exclude) {
sparseArr[t] = new int[]{i, j, arr[i][j]};
t += 1;
}
}
}
return sparseArr;
}
稀疏数组转数组
- 根据稀疏数组的
sparseArr[0]构建二维数组；
- 遍历二维数组将其初始化为默认值；
- 按行遍历稀疏数组，修改二维数组指定下标的数据；
public static int[][] restoreArr(int[][] sparseArr, int defaultValue) {
int row = sparseArr[0][0];
int column = sparseArr[0][1];
int[][] arr = new int[row][column];
if(defaultValue != 0) {
for(int i = 0; i < row; i++) {
for(int j = 0; j < column; j++) {
arr[i][j] = defaultValue;
}
}
}
for(int i = 1; i < sparseArr.length; i++) {
arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
return arr;
}
