乐趣区

关于java:稀疏数组

对于一个数组,如果大部分元素都是 0 或者其余雷同的值,只有多数不同的值时,就能够将这个数组转换稠密数组来存储,从而放大数组的规模,实现相似于压缩的性能。

转换为稠密数组

以常见的二维数组转换为稠密数组来举例,具体步骤如下:

  1. 遍历源数组,获取无效数据的个数,保留到变量 sum 中。
  2. 创立稠密数组,行数为 sum+1,列数为 3 列,第一行的三个元素别离为源数组行数,列数以及 sum,前面每一行别离为无效数据在源数组中的地位以及值。
public static int[][] arrayToSparseArray(int[][] arr){
        // 1. 获取数组中不为 0 的元素的个数
        int arrHeight = arr.length;
        int arrLength = arr[0].length;
        int sum = 0;
        for (int i = 0; i < arrHeight; i++) {for (int j = 0; j < arrLength; j++) {if (arr[i][j] != 0) {sum++;}
            }
        }

        // 2. 创立稠密数组,列数为 3,行数为 sum+1,第一行存储原数组长度,前面行存储原数组不为 0 值的地位以及值
        int[][] sparseArr = new int[sum + 1][3];
        sparseArr[0][0] = arrHeight;
        sparseArr[0][1] = arrLength;
        sparseArr[0][2] = sum;

        // 3. 将原数组中不为 0 的值存储到稠密数组中
        int count = 1;
        for (int i = 0; i < arrHeight; i++) {for (int j = 0; j < arrLength; j++) {if (arr[i][j] != 0) {sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = arr[i][j];
                    count++;
                }
            }
        }
        return sparseArr;
    }

转换为二维数组

稠密数组转换为二维数组步骤如下:

  1. 获取稠密数组第一行数据,创立二维数组。
  2. 获取稠密数组后续数据,赋值给二维数组对应元素。
public static int[][] sparseArrayToArray(int[][] sparseArr){
        // 1. 从稠密数组中获取第一行的值来创立数组
        int arrHeight = sparseArr[0][0];
        int arrLength = sparseArr[0][1];
        int[][] arr = new int[arrHeight][arrLength];

        // 2. 从稠密数组中获取值赋予给新创建的数组
        for (int i = 1; i < sparseArr.length; i++) {arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        return arr;
    }

测试

public static void main(String[] args) {
        // 创立一个二维数组
        int[][] chessArr1 = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        chessArr1[4][5] = 2;
        System.out.println("二维数组为:");
        for (int[] row : chessArr1) {for (int i : row) {System.out.printf("%d\t",i);
            }
            System.out.println();}

        System.out.println("转换为稠密数组:");
        int[][] parseArray = SparseArray.arrayToSparseArray(chessArr1);
        for (int[] row : parseArray) {for (int i : row) {System.out.printf("%d\t",i);
            }
            System.out.println();}

        System.out.println("转换为二维数组:");
        int[][] sparseArrayToArray = SparseArray.sparseArrayToArray(parseArray);
        for (int[] row : sparseArrayToArray) {for (int i : row) {System.out.printf("%d\t",i);
            }
            System.out.println();}
    }

输入如下:

 二维数组为:0    0    0    0    0    0    0    0    0    0    0    
0    0    1    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    0    0    0    0    
0    0    0    0    0    2    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
转换为稠密数组:11    11    3    
1    2    1    
2    3    2    
4    5    2    
转换为二维数组:0    0    0    0    0    0    0    0    0    0    0    
0    0    1    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    0    0    0    0    
0    0    0    0    0    2    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0

欢送关注我的公众号,一起学习技术。

退出移动版