稀疏数组的理解及与原始数组之间的相互转化的代码实现-蒲公英云

稀疏数组的理解及与原始数组之间的相互转化的代码实现

原始数组稀疏数组

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70

原始数组转稀疏数组

package com.zzb.sparsearray;
/**
 * @Auther: Administrator
 * @Date: 2020/1/7 14:44
 * @Description: 原始数组 转 稀疏数组
 * 稀疏数组 原理
 * （1）稀疏数组的第一行记录对应的原始数组总共有几行几列，对应的原始数组中有几个不同的值
 * （2）从稀疏数组的第二行开始记录对应的原始数组中不同值的元素在原始数组中的行列与值在稀疏数组中
 * 从而缩小程序的规模
 */
public class OriginalArrayToSparseArray {
    public static void main(String[] args) {
        // 定义原始数组
        int original[][] = new int[6][7];
        original[0][3] = 22;
        original[0][6] = 15;
        original[1][1] = 11;
        original[1][5] = 17;
        original[2][3] = -6;
        original[3][5] = 39;
        original[4][0] = 91;
        original[5][2] = 28;
        // 原始数组 转 稀疏数组
        int[][] sparse = originalArrayToSparseArray(original);
        // 输出由原始数组转变的稀疏数组
        for (int[] ss : sparse) {
            for (int s : ss) {
                System.out.print(s + "\t");
            }
            System.out.println();
        }
    /*  6    7    8
        0    3    22
        0    6    15
        1    1    11
        1    5    17
        2    3    -6
        3    5    39
        4    0    91
        5    2    28*/
    }
    // 原始数组 转 稀疏数组
    private static int[][] originalArrayToSparseArray(int[][] original) {
        // 遍历原始数组，得到非零数据的个数
        int sum = 0;
        for(int i = 0; i < original.length; i++) {
            for(int j = 0; j < original[i].length; j++) {
                if(original[i][j] != 0) {
                    sum++;
                }
            }
        }
        // 定义稀疏数组
        int sparse[][] = new int[sum+1][3];
        // 给稀疏数组的第一行赋值赋值
        sparse[0][0] = original.length;
        sparse[0][1] = original[0].length;
        sparse[0][2] = sum;
        // 遍历原始数组，将非零数据存储到稀疏数组中
        // count 用于记录是第几个非零数据
        int count = 0;
        for(int i = 0; i < original.length; i++) {
            for(int j = 0; j < original[i].length; j++) {
                if(original[i][j] != 0) {
                    count++;
                    sparse[count][0] = i;
                    sparse[count][1] = j;
                    sparse[count][2] = original[i][j];
                }
            }
        }
        return sparse;
    }
}

稀疏数组转原始数组

package com.zzb.sparsearray;
/**
 * @Auther: Administrator
 * @Date: 2020/1/7 13:20
 * @Description: 稀疏数组 转 原始数组
 * 稀疏数组 原理
 * （1）稀疏数组的第一行记录对应的原始数组总共有几行几列，对应的原始数组中有几个不同的值
 * （2）从稀疏数组的第二行开始记录对应的原始数组中不同值的元素在原始数组中的行列与值在稀疏数组中
 * 从而缩小程序的规模
 */
public class SparseArrayToOriginalArray {
    public static void main(String[] args) {
        // 定义稀疏数组
        int sparse[][] = new int[9][3];
        sparse[0][0] = 6;
        sparse[0][1] = 7;
        sparse[0][2] = 8;
        sparse[1][0] = 0;
        sparse[1][1] = 3;
        sparse[1][2] = 22;
        sparse[2][0] = 0;
        sparse[2][1] = 6;
        sparse[2][2] = 15;
        sparse[3][0] = 1;
        sparse[3][1] = 1;
        sparse[3][2] = 11;
        sparse[4][0] = 1;
        sparse[4][1] = 5;
        sparse[4][2] = 17;
        sparse[5][0] = 2;
        sparse[5][1] = 3;
        sparse[5][2] = -6;
        sparse[6][0] = 3;
        sparse[6][1] = 5;
        sparse[6][2] = 39;
        sparse[7][0] = 4;
        sparse[7][1] = 0;
        sparse[7][2] = 91;
        sparse[8][0] = 5;
        sparse[8][1] = 2;
        sparse[8][2] = 28;
        // 稀疏数组 转 原始数组
//        int[][] original = sparseArrayToOriginalArray(sparse);
        int[][] original = sparseArrayToOriginalArrayImprove(sparse);
        // 输出由稀疏数组转变的原始数组
        for (int[] os : original) {
            for (int o : os) {
                System.out.print(o + "\t");
            }
            System.out.println();
        }
    /*  0    0    0    22    0    0    15
        0    11    0    0    0    17    0
        0    0    0    -6    0    0    0
        0    0    0    0    0    39    0
        91    0    0    0    0    0    0
        0    0    28    0    0    0    0*/
    }
    // 稀疏数组 转 原始数组
    // 自己zzb写，时间复杂度为n^2(n*n)，因为存在双重循环，不理想，改善后只是一行代码的工作量
    private static int[][] sparseArrayToOriginalArray(int[][] sparse) {
        // 原始数组的行
        int row = 0;
        // 原始数组的列
        int col = 0;
        // 原始数组的行列所对应的值
        int value = 0;
        int original[][] = new int[sparse[0][0]][sparse[0][1]];
        for (int i = 1; i < sparse.length; i++) {
            for (int j = 0; j < sparse[i].length; j++) {
                // 获取原始数组的行
                if (j == 0) {
                    row = sparse[i][j];
                }
                // 获取原始数组的列
                if (j == 1) {
                    col = sparse[i][j];
                }
                // 获取原始数组的行列所对应的值
                if (j == 2) {
                    value = sparse[i][j];
                }
            }
            // 给原始数组赋值
            original[row][col] = value;
        }
        return original;
    }
    // 稀疏数组 转 原始数组 改善版
    private static int[][] sparseArrayToOriginalArrayImprove(int[][] sparse) {
        int original[][] = new int[sparse[0][0]][sparse[0][1]];
        for(int i = 1; i < sparse.length; i++) {
            original[sparse[i][0]][sparse[i][1]] = sparse[i][2];
        }
        return original;
    }
}