引入

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

基本介绍

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

稀疏数组-LMLPHP

代码实现

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);

}

稀疏数组-LMLPHP

  • 数组转稀疏数组
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;
}

稀疏数组-LMLPHP

  • 稀疏数组转数组
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;
}

稀疏数组-LMLPHP

04-25 12:10