专栏首页知了一笑JAVA描述算法和数据结构(01):稀疏数组和二维数组转换

JAVA描述算法和数据结构(01):稀疏数组和二维数组转换

一、基本简介

1、基础概念

在矩阵中,若数值为0的元素数目远远多于非0元素的数目,并且非0元素分布没有规律时,则称该矩阵为稀疏矩阵;与之相反,若非0元素数目占大多数时,则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。

2、处理方式

1)、记录数组一共有几行几列,有多少个不同的值
2)、把具有不同值的元素的行列及值记录在稀疏数组中,可以缩小程序代码的复杂度。

3、图解描述

稀疏数组表示
[0] 3 4 4 二维数组,3行,4列,4个非0的值;
[1] 1 2 2 一行,2列的值是2;
[2] 1 3 3 一行,3列的值是3;
…以此类推

4、五子棋场景

使用稀疏数组描述
行    列    值
[0]  11    11    2
[1]  1     2     1
[2]  2     3     2

二、代码实现

1、转换流程

二维数组转稀疏数组

1)、遍历二维数组,得到非零元素的个数
2)、创建稀疏数组
3)、二维数组的非零元素写入稀疏数组

稀疏数组转二维数组

1)、读取稀疏数组的首行,创建二维数组
2)、根据稀疏数组描述的有效元素,给二维数组赋值

2、代码实现

1)、核心流程

1、棋盘:基于二维数组
2、二维数组转稀疏数组
3、稀疏数组转二维数组

2)、方法一:生成二维数组

public static int[][] printChess (){
    // 二维数组表示 11 * 11 的棋盘,0表示没有棋,1表示 黑, 2 表示蓝
    int chessArray[][] = new int[11][11];
    chessArray[1][2] = 1;
    chessArray[2][3] = 2;
    for (int[] row : chessArray) {
        for (int data : row) {
            System.out.printf("%d\t", data);
        }
        System.out.println();
    }
    return chessArray ;
}

3)、方法二:转为稀疏数组

public static int[][] convertTwoArray (int chessArray[][]){
    // 有效元素:先遍历二维数组 得到非0数据的个数
    int unZeroSum = 0;
    for (int i = 0; i < 11; i++) {
        for (int j = 0; j < 11; j++) {
            if (chessArray[i][j] != 0) {
                unZeroSum++;
            }
        }
    }
    // 行:有效元素+1,列:3列
    int sparseArray[][] = new int[unZeroSum+1][3] ;
    sparseArray[0][0] = 11 ;// 0行0列值:11
    sparseArray[0][1] = 11 ;// 0行1列值:11
    sparseArray[0][2] = unZeroSum ;// 0行2列值:unZeroSum
    // 遍历二维数组,将非0的值存放到稀疏数组中
    // unZeroCount 用于记录是第几个非0数据,也就是稀疏数组的行
    int unZeroCount = 0; //
    for (int i = 0; i < 11; i++) {
        for (int j = 0; j < 11; j++) {
            if (chessArray[i][j] != 0) {
                unZeroCount++;
                sparseArray[unZeroCount][0] = i;
                sparseArray[unZeroCount][1] = j;
                sparseArray[unZeroCount][2] = chessArray[i][j];
            }
        }
    }
    // 输出稀疏数组的形式
    for (int i = 0; i < sparseArray.length; i++) {
        System.out.printf("%d\t%d\t%d\t\n",
                sparseArray[i][0],
                sparseArray[i][1],
                sparseArray[i][2]);
    }
    return sparseArray ;
}

4)、方法三:转为二维数组

public static void convertSparseArray (int sparseArray[][]){
    // 读取稀疏数组首行创建二维数组==>> int chessArray[][] = new int[11][11];
    int chessArray[][] = new int[sparseArray[0][0]][sparseArray[0][1]] ;
    // 非零元素赋值给二维数组
    for(int i = 1; i < sparseArray.length; i++) {
        // 几行、几列、是什么值
        chessArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
    }
    // 打印二维数组
    for (int[] row : chessArray) {
        for (int data : row) {
            System.out.printf("%d\t", data);
        }
        System.out.println();
    }
}

5)、主程序调用

public static void main(String[] args) {
    // 棋盘:基于二维数组
    int chessArray[][] = printChess () ;
    System.out.println("==========================");
    // 二维数组转稀疏数组
    int sparseArray[][] = convertTwoArray(chessArray) ;
    System.out.println("==========================");
    // 稀疏数组转二维数组
    convertSparseArray(sparseArray);
}

三、源代码地址

GitHub地址:知了一笑
https://github.com/cicadasmile/model-arithmetic-parent
码云地址:知了一笑
https://gitee.com/cicadasmile/model-arithmetic-parent

本文分享自微信公众号 - 知了一笑(cicada_smile),作者:知了一笑

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JavaEE基础(05):过滤器、监听器、拦截器,应用详解

    知了一笑
  • Java描述设计模式(09):装饰模式

    知了一笑
  • Java描述设计模式(23):访问者模式

    电竞是游戏比赛达到“竞技”层面的体育项目。利用电子设备作为运动器械进行的、人与人之间的智力对抗运动。通过电竞,可以提高人的反应能力、协调能力、团队精神等。但是不...

    知了一笑
  • 【每周一库】 pbr - Terminal progress bar for Rust

    本期的每周一库带来的是一个十分有趣的cli小工具,rust下的cli进度条库 - pbr

    MikeLoveRust
  • 洛谷P4578 [FJOI2018]所罗门王的宝藏(dfs)

    attack
  • hdu 1829 A Bug's Life(分组并查集(偏移量))

    A Bug's Life Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/3276...

    Gxjun
  • Java数组,这一篇文章就真够了

    虽然随着Java版本的演变,数组的分量在慢慢减弱,日常使用时大多使用List进行替代。但ArrayList底层依旧采用数组来进行实现,而数组依旧有很多应用的场景...

    程序新视界
  • 2018年8月29日学习mysql数据库的笔记

    今天遇到的新单词: manual n手工的 correspond v符合一致 reject v拒绝 exist  v存在 solid adj固体的 ...

    武军超
  • 如何理解数组在Java中作为一个类?【完整版】

    Java中数组的使用方法和C/C++中的比较类似,但是在Java中它的本质是一个Java类,只是这个类比较特殊,所以很容易被一些程序员误解。建议在回答该问题的时...

    田维常
  • 每天一道leetcode66-加1

    2018.11.17号打卡 明天的题目leetcode16: https://leetcode-cn.com/problems/3sum-closest/des...

    乔戈里

扫码关注云+社区

领取腾讯云代金券