稀疏数组的使用与解析

稀疏数组的概念和使用

当在一个数组中同一元素的个数远远大于数组总个数的一半以上是,可以使用稀疏数组达到元素个数的缩减,表结构清晰易懂

稀疏数组结构

稀疏数组思路:

需要得出原数组的总的行数与列数，以及每个数的多少 及其行和列 将其整合在一起

import com.sun.javaws.IconUtil;

import java.util.Scanner;

/**
 * @Description:稀疏数组的使用
 * @Author:小黑洽
 * @Date：2021/8/19
 */
public class Demo {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        /**
         * 功能描述: 
自定义数组
         * @Param: 
         * @Return: 
         * @Author: 小黑洽
         * @Date:  
         */
        int[][] array = new int[11][11];
        array[2][4] = 7;
        array[9][1] = 10;
        array[5][6] = 33;
        array[8][9] = 8;

        int count = 0;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[0].length; j++) {
                //System.out.print(array[i][j]+"  ");
                if(array[i][j] != 0){
                    count++;
                }
            }

        }

        //将二维数组转化为稀疏数组
        int[][] sparseArray = conversion(array,count);
        for (int i = 0; i < sparseArray.length; i++) {
            for (int j = 0; j < sparseArray[0].length; j++) {
                System.out.print(sparseArray [i][j]+"  ");

            }
            System.out.println();
        }

      //逆向稀疏数组
        int[][] reverseArray= reverse(sparseArray);
        for (int i = 0; i < reverseArray.length; i++) {
            for (int j = 0; j < reverseArray[0].length; j++) {
                System.out.print(reverseArray [i][j]+"  ");

            }
            System.out.println();
        }

    }

    /**
     * 功能描述: 
将二维数组转化为稀疏数组
     * @Param:
     * @Return:
     * @Author: 小黑洽
     * @Date:
     */
    public static int[][] conversion(int[][]  array,int count){

        int[][] sparseArray = new int[count+1][3];
        int t = 0;
        sparseArray[0][0]=array.length;
        sparseArray[0][1]=array[0].length;
        sparseArray[0][2]=count;
        t+=1;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[0].length; j++) {
                //System.out.print(array[i][j]+"  ");

                if(array[i][j] != 0){
                  sparseArray[t][0]=i;
                  sparseArray[t][1]=j;
                  sparseArray[t++][2]=array[i][j];

                }
            }
        }
        return sparseArray;
    }

    /**
     * 功能描述: 
稀疏数组解析
     * @Param:
     * @Return:
     * @Author: 小黑洽
     * @Date:
     */
    public static int[][]  reverse(int[][] sparseArray){
        int row = sparseArray[0][0];
        int col = sparseArray[0][1];
        int count =  sparseArray[0][2];

        int[][] reverseArray = new int[row][col];
        for (int i = 1; i < count+1 ; i++) {
           reverseArray[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2];
        }

        return reverseArray;
    }

}