初识稀疏数组

一、稀疏数组简要说明：

所谓的稀疏数组，是用于 压缩原数组 的一种数据结构。

当原数组中大部份的元素值都相同且没被使用（或都为0），仅有少部份的值是有效值（被使用）时，数组内大部份空间被浪费用于记录无效值。为了解决这问题，稀疏数组的概念的被引了出来。

稀疏数组可以理解为：只记录原数组的有效数值个数，及每个数在原数组的位置（坐标）即可。

如：

Java数组详解09 - 稀疏数组

二、稀疏数组实现方法：

  1. 稀疏数组也是一个二维数组，除去头部，稀疏数组的行数为原数组有效值的个数，列数为3；
  2. 头部，也就是第一行，array[0]行，有3列，

    array[0][0]记录原数组的行数

    array[0][1]记录原数组的列数

    array[0][2]记录原数组有效值的个数；

  3. 每行记录一个有效值在原数组的坐标及自身值。

三、稀疏数组应用实例：

如日常中最常见到的五字棋的存储：

0代表没有棋子，1代表黑棋，2代表白棋，棋盘大小为15X15

利用二维数组存储时就每个数组都必须记满11X11的所有内容，肯定会产生大量重复内容（如没子的时候都存0）。

Java数组详解09 - 稀疏数组

如上图：

  1. 先构造大小为15x15的 原数组，并按以下规律存储数据：

    0代表没有棋子，1代表黑棋，2代表白棋，棋盘大小为15X15

    示例：

    package com.zctou.array;

public class SparseArrayDemo {
    public static void main(String[] args) {
        //sparse array 稀疏数组
        //稀疏数组演示
        //1.1 构造棋盘 大小为：15x15
        int[][] arr = new int[15][15];
        //1.2 根据规则给数组赋值：0代表没有棋子，1代表黑棋，2代表白棋
        arr[1][3] = 2; //白
        arr[2][3] = 2; //白
        arr[2][4] = 1; //黑
        arr[3][3] = 1; //黑
        arr[3][4] = 2; //白
        arr[3][5] = 1; //黑
        //1.3 打印数组
        printArray(arr);


    }
    //打印数组
    public static void printArray(int[][] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[i].length; j++) {
                System.out.print(nums[i][j]+" ");
            }
            System.out.println();
        }

    }
}

    输出结果：

    0 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 2 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 2 1 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 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 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

  2. 根据稀疏数组的特点构建一个新二维数组：

      1. 头部：array[0][0]=15(15行)，array[0][1]=15（15列）,array[0][2]=6（6个棋子，就是6个有效数字）。
      2. 每行记录每一个有效数字值及其坐标（6个有效数，有6行）：

        Java数组详解09 - 稀疏数组

    • 实现代码：

      package com.zctou.array;

public class SparseArrayDemo {
    public static void main(String[] args) {
        //sparse array 稀疏数组
        //稀疏数组演示
        //1.1 构造棋盘 大小为：15x15
        int[][] arr = new int[15][15];
        //1.2 根据规则给数组赋值：0代表没有棋子，1代表黑棋，2代表白棋
        arr[1][3] = 2; //白
        arr[2][3] = 2; //白
        arr[2][4] = 1; //黑
        arr[3][3] = 1; //黑
        arr[3][4] = 2; //白
        arr[3][5] = 1; //黑
        //1.3 打印数组
        //printArray(arr);

        //2.1 构建稀疏数组 array[行数][列数]
        //列数为3（坐标x,坐标y,值）
        //行数为原数组 arr[][]的有效个数+1（表头）；
        int count = validNumsCount(arr); //有效个数
        int[][] sparseArray = new int[count+1][3];
        //2.2 按原数组来，给新数组赋值
        //2.2.1 头部：
        sparseArray[0][0] = arr.length;
        sparseArray[0][1] = arr[0].length;
        sparseArray[0][2] = count;
        //2.2.2 每行保存一个有效数的值及其坐标
        toSparseArray(arr,sparseArray);
        printArray(sparseArray);
        //System.out.println(count);

    }

    //传入原数组，及定义好长度的稀疏数组；并把原数组有效值，坐标存入稀疏数组
    public static int[][] toSparseArray(int[][] orcArray, int[][]result) {
        int n = 1;
        for (int i = 0; i < orcArray.length; i++) {
            for (int j = 0; j < orcArray[i].length; j++) {
                if(orcArray[i][j] != 0) {
                   result[n][0] = i;
                   result[n][1] = j;
                   result[n][2] = orcArray[i][j];
                   //System.out.println("i"+ i + "j" + j + orcArray[i][j]);
                   n++; //赋值完行数+1
                }
            }
        }
        return result;
    }
    //查找数组内的有效个数
    public static int validNumsCount(int[][] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[i].length; j++) {
                if(nums[i][j] != 0) {
                    count++ ;
                }
            }
        }
        return count;
    }

    //打印二维数组
    public static void printArray(int[][] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[i].length; j++) {
                System.out.print(nums[i][j]+" ");
            }
            System.out.println();
        }

    }
}

      输出：

      15 15 6 
1 3 2 
2 3 2 
2 4 1 
3 3 1 
3 4 2 
3 5 1

  3. 根据稀疏数组及相应规则，还原被压缩的数组：

      1. 根据稀疏数组表头构建原来数组 行数为：array[0][0]，列数为array[0][1]
      2. 给原数组相应位置赋值

    • 实现代码：

      package com.zctou.array;

public class SparseArrayDemo {
    public static void main(String[] args) {
        //sparse array 稀疏数组
        //稀疏数组演示

        //1.1 构造棋盘 大小为：15x15
        int[][] arr = new int[15][15];
        //1.2 根据规则给数组赋值：0代表没有棋子，1代表黑棋，2代表白棋
        arr[1][3] = 2; //白
        arr[2][3] = 2; //白
        arr[2][4] = 1; //黑
        arr[3][3] = 1; //黑
        arr[3][4] = 2; //白
        arr[3][5] = 1; //黑
        //1.3 打印数组
        //printArray(arr);

        //2.1 构建稀疏数组 array[行数][列数]
        //列数为3（坐标x,坐标y,值）
        //行数为原数组 arr[][]的有效个数+1（表头）；
        int count = validNumsCount(arr); //有效个数
        int[][] sparseArray = new int[count+1][3];
        //2.2 按原数组来，给新数组赋值
        //2.2.1 头部：
        sparseArray[0][0] = arr.length;
        sparseArray[0][1] = arr[0].length;
        sparseArray[0][2] = count;
        //2.2.2 每行保存一个有效数的值及其坐标
        sparseArray = toSparseArray(arr,sparseArray);
        //printArray(sparseArray);
        //System.out.println(count);

        //3 还原被压缩的数组
        //3.1 根据表头创建数组 newArray[][]
        int[][] newArray = new int[sparseArray[0][0]][sparseArray[0][1]]; //行与列
        //3.2 根据 sparseArray[i][0],sparseArray[i][1],sparseArray[i][2]给新数组赋值。
        for (int i = 1; i < sparseArray.length; i++) { //从稀疏数组第一行开始赢取数据
            newArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        printArray(newArray);

    }

    //传入原数组，及定义好长度的稀疏数组；并把原数组有效值，坐标存入稀疏数组
    public static int[][] toSparseArray(int[][] orcArray, int[][]result) {
        int n = 1;
        for (int i = 0; i < orcArray.length; i++) {
            for (int j = 0; j < orcArray[i].length; j++) {
                if(orcArray[i][j] != 0) {
                   result[n][0] = i;
                   result[n][1] = j;
                   result[n][2] = orcArray[i][j];
                   //System.out.println("i"+ i + "j" + j + orcArray[i][j]);
                   n++; //赋值完行数+1
                }
            }
        }
        return result;
    }
    //查找数组内的有效个数
    public static int validNumsCount(int[][] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[i].length; j++) {
                if(nums[i][j] != 0) {
                    count++ ;
                }
            }
        }
        return count;
    }

    //打印二维数组
    public static void printArray(int[][] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[i].length; j++) {
                System.out.print(nums[i][j]+" ");
            }
            System.out.println();
        }

    }
}

      输出：

      0 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 2 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 2 1 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 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 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
文章目录