稀疏数组的应用

为什么出现稀疏数组

  1. 一组数据中存才太多相同的值不同的值就那几个,如果都表示出来就将浪费很多的存储空间
  2. 数据重复太多,不能一眼看出需要的数据

稀疏数组的优点

  1. 使用稀疏数组将极大的减少空间的浪费,消除重复数据,保留有用数据‘
  2. 使数据表示更清晰,能一眼看出有用的数据

image-20221027102500729

上面这个二维数组,实际上的有效数据只有两个,我们只需要存储这两个有效数据就可以了

稀疏数组的实现方式

  1. 创建一个二维数组,第一行分别保存二维数组的行和列数
  2. 下面几行分别保存二维数组有效数据的行和列位置和有效数据
  3. 最后将创建好的稀疏数组保存在磁盘上即可

代码实现

package cn.rlfit.sparseArray;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;

public class SparseArray {

	public static void main(String[] args) {
//		创建一个二维数组,初始化为0,设置不为0的值
		int[][] array1 = new int[11][11];
		array1[1][3] = 6;
		array1[3][6] = 9;
		traversal(array1);
		System.out.println("===========转化============");
		sparse(array1);
	}
//	将数组转化为稀疏数组
	public static void sparse(int[][]  orignalArray) {
//		设置变量保存值
		int count = 0;
//		计算出二维数组的行和列
		int row = orignalArray.length;
		int low = orignalArray[0].length;
//		遍历二维数组,保存里面的值和值存在的位置
		for(int i = 0;i<orignalArray.length;i++) {
			for(int j = 0;j<orignalArray[i].length;j++) {
				if(orignalArray[i][j] !=0) {
//					保存
					count++;
				}
			}
		}
//		初始化稀疏数组
		int[][] sparseArray = new int[count+1][3];
		sparseArray[0][0] = row;
		sparseArray[0][1] = low;
		sparseArray[0][2] = count;
		int k = 0;
//		创建稀疏数组
		for(int i = 0;i<orignalArray.length;i++) {
			for(int j = 0;j<orignalArray[i].length;j++) {
				if(orignalArray[i][j] !=0) {
//					保存
					sparseArray[++k][0] = i+1;
					sparseArray[k][1] = j+1;
					sparseArray[k][2] = orignalArray[i][j];
				}
			}
		}
//		将稀数组存储到磁盘上
		File file = new File("d:/sparseArray.txt");
		FileOutputStream outputStream = null;
		try {
			 outputStream= new FileOutputStream(file);
			for(int i = 0;i<sparseArray.length;i++) {
				String str = sparseArray[i].toString();
				byte[] byt= str.getBytes();
				try {
					outputStream.write(byt);
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}finally {
			try {
				outputStream.close();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		traversal(sparseArray);
		System.out.println("============恢复===========");
		recoverArray(sparseArray);
	}
//	恢复成二维数组
	public static void recoverArray(int[][] sparseArray) {
		int row;
		int low;
		int value;
		int[][] recover = new int[sparseArray[0][0]][sparseArray[0][1]];
		for(int i = 1;i<sparseArray.length;i++) {
			row = sparseArray[i][0];
			low = sparseArray[i][1];
			value = sparseArray[i][2
			recover[row-1][low-1] = value;
		}
		traversal(recover);
	}
//	遍历数组
	public static void traversal(int[][] array) {
		for(int i = 0;i<array.length;i++) {
			for(int j = 0;j<array[i].length;j++) {
				System.out.print(array[i][j]+" ");
			}
			System.out.println();
		}
	}
}