数据结构与算法学习笔记之稀疏数组

我是阿尘。一个不想被生活放弃的野鬼。

最近在小破站找了韩顺平老师的视频，准备跟着复习一下数据结构和算法，常说好记性不如烂笔头，学过之后还是写点笔记的好。

关于稀疏数组

稀疏数组(sparse array) 是一种只为数组中的 非零元素分配内存的特殊类型数组，内存中存储了稀疏数组中非零元素的下标和值。

稀疏数组实际上就是对普通二维数组的压缩形式，当一个数组中大部分元素为0或者为同一个值时，可以使用稀疏数组来保存该数组。

稀疏数组是一个N行3列的二维数组：

1. 第一行记录普通二维数组的行数、列数和有效数据的个数
2. 剩下的N-1行记录每个有效数据所在二维数组的行数、列数和具体的值
3. 所以稀疏数组的行数N等于有效数据的个数+1

举个栗子！

1. 先创建一个8行8列的普通二维数组并给其赋值

// 创建一个二维数组
int generalArr1[][] = new int[8][8];
generalArr1[1][2] = 1;
generalArr1[2][3] = 2;
generalArr1[2][2] = 1;

​ 这个数组的打印出来的样式

// 遍历二维数组并输出
for (int[] rows : generalArr1) {
    for (int data : rows) {
        System.out.printf("%d\t", data);
    }
    System.out.println();
}

1. 将此二维数组转换成稀疏数组

// 二维数组转稀疏数组
// 1.遍历二维数组，得到有效数据的个数
int sum = 0;// 初始化有效数据的个数
for (int i = 0; i < 8; i++) {
    for (int j = 0; j < 8; j++) {
        if (generalArr1[i][j] != 0) {
            sum++;
        }
    }
}
// 2.创建稀疏数组
int sparseArr[][] = new int[sum + 1][3];
sparseArr[0][0] = 8;
sparseArr[0][1] = 8;
sparseArr[0][2] = sum;
// 3.遍历二维数组，将非零数据存入sparseArr中
int count = 0;
for (int i = 0; i < 8; i++) {
    for (int j = 0; j < 8; j++) {
        if (generalArr1[i][j] != 0) {
            count++;
            sparseArr[count][0] = i;
            sparseArr[count][1] = j;
            sparseArr[count][2] = generalArr1[i][j];
        }
    }
}

转换后的稀疏数组

// 3.输出稀疏数组
for (int i = 0; i < sparseArr.length; i++) {
    System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
}

1. 稀疏数组转回二维数组

// 稀疏数组转二维数组
// 1.创建一个二维数组
int generalArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
// 2.读取稀疏数组的数据并赋给二维数组
for (int i = 1; i < sparseArr.length; i++) {
    generalArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}

总结一下

二维数组转稀疏数组的思路：

1. 遍历二维数组得到有效数据的个数sum
2. 得到sum之后就可以创建稀疏数组sparseArr[sum+1][3]
3. 将二维数组的行数、列数和有效数据个数存入稀疏数组的第一行
4. 将二维数组的有效数据所在行数、列数和值存入之后的行

稀疏数组转二维数组的思路：

1. 读取稀疏数组第一行，根据第一行的数据创建二维数组generalArr2[sparseArr[0][0]] [sparseArr[0][1]]

2. 读取稀疏数组后几行的数据赋给二维数组

3. 读取稀疏数组第一行，根据第一行的数据创建二维数组generalArr2[sparseArr[0][0]] [sparseArr[0][1]]

4. 读取稀疏数组后几行的数据赋给二维数组