稀疏数组如何高效存储和检索数据？

本文共计1223个文字，预计阅读时间需要5分钟。

1. 简单数组与数组+1基本功能：当数组中大部分元素为同一值时，可以表示为[0, ..., 0, n]，其中n为数组长度。或者，当数组中存在相同值时，可以表示为[0, ..., 0, value]，其中value为相同值。

2. 处理方法记录数组：记录数组中的元素及其出现次数。

一、稀疏数组和队列

1、稀疏数组

基本功能

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

2.处理方法

• 记录数组一共有几行几列，有多少个不同的值
• 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

如图，把一个6X7的二维数组变为了一个9X3的稀疏数组。其中

• 第一行保存的是原二维数组的行、列以及非0值的个数
• 第二到九行保存的是每个非0值所在的位置及其数值

3.转换思路

二维数组转稀疏数组

• 遍历二维数组，得到二维数组中有效值的个数sum
• 创建稀疏数组，有sum+1行，3列（固定）
• 将二维数组中的有效值存入稀疏数组中

稀疏数组转二维数组

• 先读取稀疏数组的第一行（保存二维数组的行列信息），还原二维数组
• 读取稀疏数组的其他行，将值赋给二维数组的对应位置上的数

代码

public class Demo2 { public static void main(String[] args) { //创建一个二维数组 int[][] arr1 = new int[11][11]; //向二维数组里放值 arr1[1][2] = 1; arr1[2][3] = 2; arr1[3][4] = 3; //打印二维数组 System.out.println("遍历二维数组"); for (int i = 0; i < arr1.length; i++) { for (int j = 0; j < arr1[0].length; j++) { System.out.print(arr1[i][j] + " "); } System.out.println(); } //二位数组----->稀疏数组 //遍历二维数组中有效值的个数,用sum来记录 int sum = 0; for (int i = 0; i < arr1.length; i++) { for (int j = 0; j < arr1[0].length; j++) { if (arr1[i][j] != 0) { //二维数组中元素不为0即为有效值 sum++; } } } //创建稀疏数组 //行数为sum+1，第一行用于保存二维数组的行列及有效值个数，列数固定为3 int[][] sparseArr = new int[sum + 1][3]; //存入二维数组的行列及有效值个数 sparseArr[0][0] = arr1.length; sparseArr[0][1] = arr1[0].length; sparseArr[0][2] = sum; //再次遍历二维数组，将有效值存入稀疏数组 //用于保存稀疏数组的行数 int count = 1; for (int i = 0; i < arr1.length; i++) { for (int j = 0; j < arr1[0].length; j++) { if (arr1[i][j] != 0) { //将值存入稀疏数组 sparseArr[count][0] = i; sparseArr[count][1] = j; sparseArr[count][2] = arr1[i][j]; count++; } } } //打印稀疏数组 System.out.println("遍历稀疏数组"); for (int i = 0; i < sparseArr.length; i++) { for (int j = 0; j < sparseArr[0].length; j++) { System.out.print(sparseArr[i][j] + " "); } System.out.println(); } //稀疏数组------>二维数组 //先得到二位数组的行列数 int row = sparseArr[0][0]; int col = sparseArr[0][1]; int[][] arr2 = new int[row][col]; //遍历稀疏数组，同时给二维数组赋值 for (int i = 1; i < sparseArr.length; i++) { row = sparseArr[i][0]; col = sparseArr[i][1]; //该位置上对应的值 int val = sparseArr[i][2]; arr2[row][col] = val; } //打印二维数组 System.out.println("遍历还原后的二维数组"); for (int i = 0; i < arr2.length; i++) { for (int j = 0; j < arr2[0].length; j++) { System.out.print(arr2[i][j] + " "); } System.out.println(); } } }

运行结果

遍历二维数组 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 遍历稀疏数组 11 11 3 1 2 1 2 3 2 3 4 3 遍历还原后的二维数组 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0