数据结构之稀疏数组

稀疏数组

分析问题：因为该数组很多值都是默认0，因此记录了很多无用的数据->稀疏数组。

稀疏数组处理方式：

1. 记录数组一共有几行几列。

2. 把具有不同值的元素的行列及值记录在一个小规模数组中，从而缩小程序规模

example:

代码实现:

package com.lyx.day1;

import java.util.Arrays;

/**
 * @author liao
 * @date 2022/9/16 19:12
 */
public class Test01 {

    /**
     * 稀疏数组
     * @param args
     */
    public static void main(String[] args) {
        int[][] arr = new int[11][11];
        arr[1][2] = 1;
        arr[2][3] = 2;
        for (int[] ints : arr) {
            for (int anInt : ints) {
                System.out.print(" "+anInt);
            }
            System.out.println();
        }
        int sum = 0;
        //获取有效个数
        for (int[] ints : arr) {
            for (int anInt : ints) {
                if(anInt != 0){
                    sum++;
                }
            }
        }
        //有效数据个数
        System.out.println("sum == "+sum);

        int[][] xishu = new int[sum + 1][sum + 1];
        //给稀疏数组赋值
        xishu[0][0] = 11;
        xishu[0][1] = 11;
        xishu[0][2] = sum;
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if(arr[i][j] != 0){
                    count++;
                    xishu[count][0] = i;
                    xishu[count][1] = j;
                    xishu[count][2] = arr[i][j];
                }
            }
        }
        //遍历稀疏数组
        for (int[] ints : xishu) {
            for (int anInt : ints) {
                System.out.print(" " + anInt);
            }
            System.out.println();
        }
        //将稀疏数组恢复成二位数组
        int[][] ints = new int[xishu[0][0]][xishu[0][1]];

        for (int i = 1; i < xishu.length; i++) {
            ints[xishu[i][0]][xishu[i][1]] = xishu[i][xishu[i].length-1];
        }

        System.out.println("开始打印转换为二位数组的稀疏数组");
        //遍历转换为稀疏数组的二位数组
        for (int[] anInt : ints) {
            for (int i : anInt) {
                System.out.print(" "+i);
            }
            System.out.println();
        }

    }

}