稀疏 sparsearray 数组

基本介绍

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

稀疏数组的处理方法是:

· 记录数组一共有几行几列，有多少个不同的值

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

实际需求

应用案例

1) 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)

2) 把稀疏数组存盘，并且可以从新恢复原来的二维数组数

3) 整体思路分析

4) 代码实现

package com.tuling.sparearray;

/**
 * 
 * @ClassName SparseArrayDemo1
 * @Description 稀疏数组
 * @Author 北京图灵学院
 */
public class SparseArrayDemo1 {

	public static void main(String[] args) {
		// ------------------- 1、准备原始数据 -------------------
		int sourceArray[][] = new int[9][7];
		sourceArray[1][1] = 23;
		sourceArray[2][6] = 8;
		sourceArray[2][2] = 11;
		sourceArray[4][3] = 14;
		sourceArray[4][6] = 76;
		sourceArray[5][4] = 44;
		sourceArray[6][0] = 43;
		sourceArray[8][5] = 32;

		// 遍历原始数组
		for (int[] row : sourceArray) {
			for (int data : row) {
				System.out.print(data + "\t");
			}
			System.out.println();
		}
		System.out.println();
		System.out.println();
		
		
		
		// ------------------- 2、将原始数组转换为稀疏数组 -------------------
		int sparse[][] = arrayConvertToSparse(sourceArray);
		System.out.println("转换后的稀疏数组为：");
		for (int[] row : sparse) {
			for (int data : row) {
				System.out.print(data + "\t");
			}
			System.out.println();
		}
		System.out.println();
		System.out.println();
		
		
		
		// ------------------- 3、将稀疏数组转换为原始数组 -------------------
		int sourceArr2[][] = sparseConvertToArray(sparse);
		System.out.println("还原的二维数组为：");
		for (int[] row : sourceArr2) {
			for (int data : row) {
				System.out.print(data + "\t");
			}
			System.out.println();
		}
		
	}

	/**
	 * 将原始的二维数组转换为稀疏数组 
	 * 思路： 
	 * 	1、先遍历原始数组，获取到有效数据的个数。
	 * 	2、根据有效数据的个数，创建对应的稀疏数组。（sum+1)作为稀疏数组的行 
	 * 	3、遍历原始数组，将数据存入到稀疏数组中。
	 * 
	 * @param sourceArray:原始二维数组
	 * @return sparseArr:稀疏数组
	 */
	public static int[][] arrayConvertToSparse(int[][] sourceArray) {
		// 定义一个遍历记录有效数据的个数
		int sum = 0;
		// 1、先遍历原始的二维数组。
		for (int i = 0; i < sourceArray.length; i++) {
			for (int j = 0; j < sourceArray[i].length; j++) {
				if (sourceArray[i][j] != 0) {
					// 需要将有效数据的个数+1
					sum++;
				}
			}
		}

		// 2、根据有效数据的个数创建对应的稀疏数组。
		int sparseArr[][] = new int[sum + 1][3];
		sparseArr[0][0] = sourceArray.length;
		sparseArr[0][1] = sourceArray[0].length;
		sparseArr[0][2] = sum;
		

		// 3、遍历原始数组，将有效数据存入到稀疏数组中。
		// 定义一个变量，记录当前为第几行
		int count = 0;
		for (int i = 0; i < sourceArray.length; i++) {
			for (int j = 0; j < sourceArray[i].length; j++) {
				if (sourceArray[i][j] != 0) {
					count++;
					sparseArr[count][0] = i;
					sparseArr[count][1] = j;
					sparseArr[count][2] = sourceArray[i][j];
				}
			}
		}

		return sparseArr;
	}
	
	
	/**
	 * 将稀疏数组还原为二维数组
	 * 思路：
	 * 	1、根据稀疏数组的第一行数据，创建二维数组。
	 * 	2、遍历稀疏数组，将数据插入到二维数组中
	 * 	3、return
	 * @param sparseArr:稀疏数组
	 * @return sourceArr:二维数组
	 */
	public static int[][] sparseConvertToArray(int[][] sparseArr){
		//根据稀疏数组的第一行数据，创建二维数组。
		int sourceArr[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
		
		//2、从1下标位置开始遍历稀疏数组，将数据插入到二维数组中.
		for (int i = 1; i < sparseArr.length; i++) {
			for (int j = 0; j < sparseArr[i].length; j++) {
				sourceArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][j];
			}
		}
		return sourceArr;
	}
}

今天的文章稀疏 sparsearray 数组分享到此就结束了，感谢您的阅读。