线性结构:稀疏数组
1. 稀疏数组介绍
当一个二维数组中大部分元素为0时,可以使用稀疏数组来保存该数组的信息,通过减少原数组中0的个数,以达到减小原数组的大小,具体处理方法如下:
建立一个全新的二维数组,第一行存储原数组的行数、列数以及非零元素个数,其中,非零元素个数用于确定存储数组数据的行数。
我们只需要循环遍历原数组,遇到非零元素将其加入到稀疏数组第二部分的存储数组数据区即可。
2. 稀疏数组实现
代码实现:
package com.caochenlei.array;
public class SparseArray {
public static void main(String[] args) {
//创建一个测试二维数组
int[][] testArray = createArray();
showArray("创建一个测试二维数组", testArray);
//原数组转换为稀疏数组
int[][] sparseArray = toSparseArray(testArray);
showArray("原数组转换为稀疏数组", sparseArray);
//稀疏数组转换为原数组
testArray = toOriginalArray(sparseArray);
showArray("稀疏数组转换为原数组", testArray);
}
/**
* 打印二维数组的信息
*
* @param message 提示信息
* @param array 二维数组
*/
public static void showArray(String message, int[][] array) {
System.out.println(message + ":");
for (int[] row : array) {
for (int col : row) {
System.out.printf("%d\t", col);
}
System.out.println();
}
System.out.println();
}
/**
* 创建测试的二维数组
*
* @return 二维数组
*/
public static int[][] createArray() {
int testArray[][] = new int[10][10];
testArray[1][1] = 1;
testArray[1][2] = 2;
testArray[2][3] = 3;
return testArray;
}
/**
* 原数组转换为稀疏数组
*
* @param array 原数组
* @return 稀疏数组
*/
public static int[][] toSparseArray(int[][] array) {
//获取原数组的行数
int rows = array.length;
//获取原数组的列数
int cols = array[0].length;
//获取非零元素个数
int sum = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (array[i][j] != 0) {
sum++;
}
}
}
//创建一个稀疏数组
int sparseArray[][] = new int[1 + sum][3];
//第一部分信息赋值
sparseArray[0][0] = rows;
sparseArray[0][1] = cols;
sparseArray[0][2] = sum;
//第二部分数据赋值
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (array[i][j] != 0) {
count++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = array[i][j];
}
}
}
//返回一个稀疏数组
return sparseArray;
}
/**
* 稀疏数组转换为原数组
*
* @param sparseArray 稀疏数组
* @return 原数组
*/大连妇科医院哪家好 https://m.120ask.com/zhenshi/dlfk/
public static int[][] toOriginalArray(int[][] sparseArray) {
//获取原数组的行数
int rows = sparseArray[0][0];
//获取原数组的列数
int cols = sparseArray[0][1];
//恢复原数组的数据
int testArray[][] = new int[rows][cols];
for (int i = 1; i < sparseArray.length; i++) {
int row = sparseArray[i][0];
int col = sparseArray[i][1];
int val = sparseArray[i][2];
testArray[row][col] = val;
}
//返回一个原数组
return testArray;
}
}
运行效果:
创建一个测试二维数组:
0 0 0 0 0 0 0 0 0 0
0 1 2 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
原数组转换为稀疏数组:
10 10 3
1 1 1
1 2 2
2 3 3
稀疏数组转换为原数组:
0 0 0 0 0 0 0 0 0 0
0 1 2 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
![](https://res.hc-cdn.com/ecology/9.3.130/v2_resources\images\global\blog-dialog.png)
华为开发者空间发布
让每位开发者拥有一台云主机
- 点赞
- 收藏
- 关注作者
评论(0)