稀疏数组

定义

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

稀疏数组为二维数组。

sparseArray[0] [0]代表原数组的行数

sparseArray[0] [1]代表原数组列数

sparseArray[0] [2]代表原数组非零值的个数

sparseArray[!=0] []开始记录非零元素的数据

sparseArray[!=0] [0]为其中一个非零元素所在的行索引。

sparseArray[!=0] [1]为其中一个非零元素所在的列索引。

sparseArray[!=0] [2]为其中一个非零元素的值。

代码实现

int[][] myArray = new int[11][11];
        myArray[1][2] = 1;
        myArray[2][3] = 2;

得到二维数组：

转换为稀疏数组思路

1. 遍历原数组，再结合if判断得到原数组非零元素个数。

2. 非零元素个数+1为稀疏数组行数。（多一列用于存储原列表的长度）。

3. 非零元素个数，为稀疏数组[0] [2]的数据。

4. 通过遍历获得原数组的行列数，为稀疏数组[0] [0]和稀疏数组[0] [1]的数据。

5. 定义一个临时变量存储原数组的非零元素，再一次遍历原数组（第一次遍历为了创造稀疏数组，第二次遍历将原数组数据存入稀疏数组）。

6. 当遍历到非零元素时，当前原数组的二位长度[i] [j]即为稀疏数组的[!=0] [0]和[!=0] [1],当前元素为[!=0] [2]。

/**
 * 将原数组转换为稀疏数组。
 * @param myArray 为原数组。
 */
public sparseArray(int[][] myArray) {
    int sum = 0;
    for (int[] ints : myArray) {
        for (int j = 0; j < myArray[0].length; j++) {
            if (ints[j] != 0) {
                sum++;
            }
        }
    }
    int[][] array = new int[sum + 1][3];
    this.array = array;
    array[0][0] = myArray.length;
    array[0][1] = myArray[0].length;
    array[0][2] = sum;
    int count = 0;
    for (int i = 0; i < myArray.length; i++) {
        for (int j = 0; j < myArray[0].length; j++) {
            if (myArray[i][j] != 0) {
                count++;
                array[count][0] = i;
                array[count][1] = j;
                array[count][2] = myArray[i][j];
            }
        }
    }
}

稀疏数组还原成普通二维数组思路

1. 新建二维数组，长度为稀疏数组的[0] [0],[0] [1]。

2. 读取稀疏数组每行内容（从第二行开始读取，第一行为普通二维数组的长度）。

3. 在普通二维数组的对应位置赋值，普通二维数组的[稀疏数组[!=0] [0]] [稀疏数组[!=0] [1]]值为稀疏数组[!=0] [2]。

/**
 * 将稀疏数组还原成普通二维数组。
 * @return 普通二维数组
 */
public int[][] toArray(){
    int [][] myArray = new int[array[0][0]][array[0][1]];
    for (int i = 1; i < array.length; i++) {
        myArray[array[i][0]][array[i][1]] = array[i][2];
    }
    return myArray;
}

完整代码

class sparseArray {
    int[][] array;

    /**
     * 将原数组转换为稀疏数组。
     * @param myArray 为原数组。
     */
    public sparseArray(int[][] myArray) {
        int sum = 0;
        for (int[] ints : myArray) {
            for (int j = 0; j < myArray[0].length; j++) {
                if (ints[j] != 0) {
                    sum++;
                }
            }
        }
        int[][] array = new int[sum + 1][3];
        this.array = array;
        array[0][0] = myArray.length;
        array[0][1] = myArray[0].length;
        array[0][2] = sum;
        int count = 0;
        for (int i = 0; i < myArray.length; i++) {
            for (int j = 0; j < myArray[0].length; j++) {
                if (myArray[i][j] != 0) {
                    count++;
                    array[count][0] = i;
                    array[count][1] = j;
                    array[count][2] = myArray[i][j];
                }
            }
        }
    }


    public void printArray(int[][] array) {
        System.out.println("数组为~~~~~~~~~~~~");
        for (int[] row : array) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }
    public void printArray() {
        System.out.println("数组为~~~~~~~~~~~~");
        for (int[] ints : array) {
            System.out.printf("%d\t%d\t%d\t\n", ints[0], ints[1], ints[2]);
        }
    }

    /**
     * 将稀疏数组还原成普通二维数组。
     * @return 普通二维数组
     */
    public int[][] toArray(){
        int [][] myArray = new int[array[0][0]][array[0][1]];
        for (int i = 1; i < array.length; i++) {
            myArray[array[i][0]][array[i][1]] = array[i][2];
        }
        return myArray;
    }
}