概述
稀疏数组也是一种数组 (总是二维的), 是一种多维数组的数组压缩技术. 比如存在一个 的数组, 但是数组中只有 3 个元素, 如果要存储的话需要占 100 个位置. 因为数组的每个位置的元素都要存储, 哪怕是 0 或者 null.
稀疏数组就是为了解决这个问题的. 稀疏数组的第一行存储数组的维度信息以及有效元素数. 剩余行存储有效元素所在的坐标和元素的值. 如上二维数组, 那么采用稀疏数组存储就是:
稀疏数组的行数是: 有效元素数 + 1; 列数是: 数组维度 + 1. 如果是一个 3 维数组, 那就需要 4 列来保存数据, 因为有 3 列要保存元素的坐标.
从上面的例子我们可以看出, 稀疏数组存储的数据所占用的位置要比二维数组小很多, 上面的 的数组占了 100 个位置, 而使用稀疏数组后仅用了 16 个位置.
什么情况下才可以用稀疏数组
然而稀疏数组并不总是好的, 从上面的例子中我们也看出来了, 稀疏数组只适合于有效数据少, 但是数组较大的情况. 假设一个二维数组行是 列是 有 个有效数据, 那么稀疏数组的行数就是, 列数是 3, 所以只有在
时, 使用稀疏数组才能有效的对数据进行压缩. 对于上面 的数组就是 32, 如果超过 32 个有效元素, 使用稀疏数组反而会增加开销.
那么推广到多维数组, 假设 维数组可以存储 个元素, 数组中有 个有效元素. 那么稀疏数组的行数就是, 列数是. 只有在
对于一个 3 维可存放 1000 个元素的数组, 只有当有效元素小于 时, 适用稀疏数组才能起到节省空间的作用.
实现
以下列出 Java 中二维稀疏数组的实现.
- package com.codestd.study.ds;
- /**
- * 稀疏数组
- *
- * @author jaune
- * @since 1.0.0
- */
- public class SparseArray {
- /**
- * 将一个二维数组转成稀疏数组
- * @param arrs 二维数组
- * @return 稀疏数组
- */
- public int[][] toSparse(int[][] arrs) {
- //arrs.length;
- int row = arrs.length, col = arrs[0].length, nums = 0;
- for (int[] arr : arrs) {
- for (int i : arr) {
- if (i != 0) {
- nums++;
- }
- }
- }
- int[][] sparseArr = new int[nums + 1][3];
- sparseArr[0][0] = row;
- sparseArr[0][1] = col;
- sparseArr[0][2] = nums;
- int index = 1;
- for (int i = 0; i < row; i++) {
- for (int j = 0; j < col; j++) {
- int num = arrs[i][j];
- if (num != 0) {
- sparseArr[index][0] = i;
- sparseArr[index][1] = j;
- sparseArr[index][2] = num;
- index++;
- }
- }
- }
- return sparseArr;
- }
- /**
- * 将一个稀疏数组转为二维数组
- * @param sparseArr 稀疏数组, 这里稀疏数组需要是一个二维数组的稀疏数组.
- * @return 还原后的二维数组
- */
- public int[][] parse(int[][] sparseArr) {
- int row = sparseArr[0][0],
- col = sparseArr[0][1],
- nums = sparseArr[0][2];
- int[][] arr = new int[row][col];
- for (int i = 1; i <= nums; i++) {
- int[] ints = sparseArr[i];
- arr[ints[0]][ints[1]] = ints[2];
- }
- return arr;
- }
- /**
- * 测试一下
- * @param args
- */
- public static void main(String[] args) {
- SparseArray sparseArray = new SparseArray();
- int[][] arrs = new int[11][11];
- arrs[2][3] = 10;
- arrs[3][6] = 20;
- int[][] sparseArr = sparseArray.toSparse(arrs);
- System.out.println(sparseArr);
- int[][] sourceArr = sparseArray.parse(sparseArr);
- System.out.println(sourceArr);
- }
- }
对于 的二维数组, toSparse()的时间复杂度为 (如果不知道这里为什么等于 可以看看我个人博客上关于算法复杂度的文章).parse()方法的时间复杂度是, 这个 n 是有效元素数()
应用
如棋盘的保存. 围棋或者五子棋, 要把棋盘上落子的信息保存起来.
来源: http://www.jianshu.com/p/8693b7108a62