数据结构与算法（1）-稀疏数组
概念
所谓稀疏数组就是数组中大部分的内容值都未被使用（或都为零），在数组中仅有少部分的空间使用。因此造成内存空间的浪费，为了节省内存空间，并且不影响数组中原有的内容值，我们可以采用一种压缩的方式来表示稀疏数组的内容
问题
需要将原始数组转换成二维数组是关键。
实现
二维数组转稀疏数组的思路：
1.遍历数组,得到有效数据的个数sum,得到原始数组的大小。
2.根据sum的值创建稀疏数组sparseArray，次数组的一共有3列 ，根据sum的值确定有多少行。
3.将二维数组的有效数据存入到稀疏数组中。package io.gjf.T01_Sparsearray;
/**
* Create by GuoJF on 2019/12/16
*/
public class App {
public static void main(String[] args) {
/*
*
* 首先创建原始数组
* */
int[][] originalArray = new int[9][9];
/*
* 手动为数组中的两个位置赋值
* */
originalArray[0][1] = 1;
originalArray[2][1] = 2;
for (int[] values : originalArray) {
for (int value : values) {
System.out.print(value + "\t");
}
System.out.println();
}
/*
* 获取到数组的长度 | 纵向长度
* */
int length = originalArray.length;
/*
* 获取到数组的 "宽"度 | 横向长度
* */
int width = originalArray[1].length;
/*
* 设置count 存储有效值个数
* */
int count = 0;
/*
* 获取数组中有几个有效值
* */
for (int[] values : originalArray) {
for (int value : values) {
if (value != 0) {
count++;
}
}
}
/*
* 创建稀疏数组
* */
int[][] sparseArray = new int[count + 1][3];
/*
* 设置稀疏数组第一行的值
* */
sparseArray[0][0] = length;
sparseArray[0][1] = width;
sparseArray[0][2] = count;
int cycleNum = 0;
for (int i = 0; i < originalArray.length; i++) {
for (int j = 0; j < originalArray.length; j++) {
int currentValue = originalArray[i][j];
if (currentValue != 0) {
sparseArray[cycleNum + 1][0] = i;
sparseArray[cycleNum + 1][1] = j;
sparseArray[cycleNum + 1][2] = currentValue;
cycleNum++;
}
}
}
for (int[] values : sparseArray) {
for (int value : values) {
System.out.print(value + "\t");
}
System.out.println();
}
}
}
运行结果
0 1 0 0 0 0 0 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 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
9 9 2
0 1 1
2 1 2 稀疏数组转二维数组的思路：
1.先读取稀疏数组的第一行，得到元数据的有几行几列以及有多少个值，创建原始数组。
2.再读取稀疏数组的后几行的数据， 并赋值给原始的二维数组。package io.gjf.T01_Sparsearray;
/**
* Create by GuoJF on 2019/12/16
*/
public class App_SpareArrayToOriginal {
public static void main(String[] args) {
int[][] sparseArray = new int[3][3];
sparseArray[0][0] = 9;
sparseArray[0][1] = 9;
sparseArray[0][2] = 2;
sparseArray[1][0] = 0;
sparseArray[1][1] = 1;
sparseArray[1][2] = 1;
sparseArray[2][0] = 2;
sparseArray[2][1] = 1;
sparseArray[2][2] = 2;
for (int[] values : sparseArray) {
for (int value : values) {
System.out.print(value + "\t");
}
System.out.println();
}
/*
* 得到原始数组的长度
* 得到原始数组的宽度
* */
int length = sparseArray[0][0];
int width = sparseArray[0][1];
int valueSum = sparseArray[0][2];
int[][] originalArray = new int[length][width];
for (int i = 0; i < valueSum; i++) {
int i0 = sparseArray[i + 1][0];
int i1 = sparseArray[i + 1][1];
int i2 = sparseArray[i + 1][2];
originalArray[i0][i1] = i2;
}
for (int[] values : originalArray) {
for (int value : values) {
System.out.print(value + "\t");
}
System.out.println();
}
}
}
9 9 2
0 1 1
2 1 2
0 1 0 0 0 0 0 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 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
版权声明：本文为iamgjf原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。