稀疏数组

引入

• 我们应该怎么实现 ？
  • 以围棋举例
    • 使用二维数组将棋盘记下 ，如 0 为 没有棋子 ，1 为 黑子 ， 2为白子
  • 但是没有棋子的地方都为 0 ，整个二维数组充斥着大量的无效数据 0
  • 我们需要想一个办法来 优化存储的方式

基本介绍

• 稀疏数组：是将一个有效元素 的 坐标 和 值 记录在一个小规模数组中
  • 该有效数组的头部(第一行)
    • 记录了原数组一个 有几行，几列，有多少个有效值
  • 该数组剩下的行数
    • 是由有效值的个数来决定的 ，即 一个有效数占据一行

代码实现

SparseArray.java

• main方法

public static void main(String[] args) {
    // 定义一个全是0的数组
    int[][] array = new int[11][11];
    // 向数组中添加几个 有效元素
    array[2][3] = 1;
    array[3][4] = 2;
    array[2][5] = 2;
    array[5][5] = 2;
    // 遍历该数组查看效果
    for (int[] row : array) {
        for (int data : row) {
            System.out.print(data + "  ");
        }
        System.out.println();
    }
    int[][] sparse = toSparseArray(array);
    int[][] toArray = toArray(sparse);

}

• 数组转稀疏数组

public static int[][] toSparseArray(int[][] array) {
    /*
     *  思路：
     *   1.根据传入的二维数组，创建稀疏数组
     *   2.遍历二维数组 ，如果当前元素值为有效值(不为0) ，就将该元素的坐标和值保存到稀疏数组中
     *   3.因为需要坐标，所以使用普通for循环
     */

    // 1. 根据传入的二维数组创建稀疏数组 ，并给稀疏数组第一行赋值

    // 1.1 遍历二维数组，获取有效元素个数
    int num = 0;
    for (int i = 0; i < array.length; i++) {
        int[] row = array[i];
        for (int j = 0; j < row.length; j++) {
            if (row[j] != 0) {
                num++;
            }
        }
    }
    // 1.2 创建稀疏数组
    int[][] sparse = new int[num + 1][3];

    // 1.3 给稀疏数组第一行赋值
    sparse[0][0] = array.length;   // 原数组行数
    sparse[0][1] = array[0].length;      // 原数组列数
    sparse[0][2] = num;               // 有效元素个数值


    // 2.1 定义一个值 ，记录稀疏数组实际的行数
    num = 0;

    // 2.2  再次遍历二维数组 ，并给稀疏数组赋值
    for (int i = 0; i < array.length; i++) {
        int[] row = array[i];
        for (int j = 0; j < row.length; j++) {
            if (row[j] != 0) {
                ++num;
                sparse[num][0] = i;
                sparse[num][1] = j;
                sparse[num][2] = array[i][j];
            }
        }
    }
    // 遍历该数组查看效果
    for (int[] row : sparse) {
        for (int data : row) {
            System.out.print(data + "  ");
        }
        System.out.println();
    }

    return sparse;
}

• 稀疏数组转数组

private static int[][] toArray(int[][] sparse) {
    // 根据稀疏数组的第一行，创建二维数组
    int[][] array = new int[sparse[0][0]][sparse[0][1]];

    // 遍历稀疏数组 ，从第二行开始将稀疏数组中的值 赋给 创建好的二维数组
    for (int i = 1; i < sparse.length; i++) {
        int[] row = sparse[i];
        array[row[0]][row[1]]=row[2];
    }

    // 遍历二维数组，打印值
    for (int[] row : array) {
        for (int data : row) {
            System.out.print(data + "  ");
        }
        System.out.println();
    }
    return array;
}