稀疏数组

引入

  • 当在网页上下棋类游戏时,玩到中途想要离开,但是我们需要保存进度,方便下次继续
  • 我们应该怎么实现 ?
    • 以围棋举例
      • 使用二维数组将棋盘记下 ,如 0 为 没有棋子 ,1 为 黑子 , 2为白子
    • 但是没有棋子的地方都为 0 ,整个二维数组充斥着大量的无效数据 0
    • 我们需要想一个办法来 优化存储的方式

基本介绍

  • 当一个数组中大部分元素是同一个值时,我们可以使用稀疏数组来保存该数组
  • 稀疏数组:是将一个有效元素 的 坐标 和 值 记录在一个小规模数组中
    • 该有效数组的头部(第一行)
      • 记录了原数组一个 有几行,几列,有多少个有效值
    • 该数组剩下的行数
      • 是由有效值的个数来决定的 ,即 一个有效数占据一行

稀疏数组图示.png

代码实现

SparseArray.java

  • main方法
public static void main(String[] args) {
    // 定义一个全是0的数组
    int[][] array = new int[11][11];
    // 向数组中添加几个 有效元素
    array[2][3] = 1;
    array[3][4] = 2;
    array[2][5] = 2;
    array[5][5] = 2;
    // 遍历该数组查看效果
    for (int[] row : array) {
        for (int data : row) {
            System.out.print(data + "  ");
        }
        System.out.println();
    }
    int[][] sparse = toSparseArray(array);
    int[][] toArray = toArray(sparse);

}

二维数组转稀疏数组.png

  • 数组转稀疏数组
public static int[][] toSparseArray(int[][] array) {
    /*
     *  思路:
     *   1.根据传入的二维数组,创建稀疏数组
     *   2.遍历二维数组 ,如果当前元素值为有效值(不为0) ,就将该元素的坐标和值保存到稀疏数组中
     *   3.因为需要坐标,所以使用普通for循环
     */

    // 1. 根据传入的二维数组创建稀疏数组 ,并给稀疏数组第一行赋值

    // 1.1 遍历二维数组,获取有效元素个数
    int num = 0;
    for (int i = 0; i < array.length; i++) {
        int[] row = array[i];
        for (int j = 0; j < row.length; j++) {
            if (row[j] != 0) {
                num++;
            }
        }
    }
    // 1.2 创建稀疏数组
    int[][] sparse = new int[num + 1][3];

    // 1.3 给稀疏数组第一行赋值
    sparse[0][0] = array.length;   // 原数组行数
    sparse[0][1] = array[0].length;      // 原数组列数
    sparse[0][2] = num;               // 有效元素个数值


    // 2.1 定义一个值 ,记录稀疏数组实际的行数
    num = 0;

    // 2.2  再次遍历二维数组 ,并给稀疏数组赋值
    for (int i = 0; i < array.length; i++) {
        int[] row = array[i];
        for (int j = 0; j < row.length; j++) {
            if (row[j] != 0) {
                ++num;
                sparse[num][0] = i;
                sparse[num][1] = j;
                sparse[num][2] = array[i][j];
            }
        }
    }
    // 遍历该数组查看效果
    for (int[] row : sparse) {
        for (int data : row) {
            System.out.print(data + "  ");
        }
        System.out.println();
    }

    return sparse;
}

二维数组转稀疏数组.png

  • 稀疏数组转数组
private static int[][] toArray(int[][] sparse) {
    // 根据稀疏数组的第一行,创建二维数组
    int[][] array = new int[sparse[0][0]][sparse[0][1]];

    // 遍历稀疏数组 ,从第二行开始将稀疏数组中的值 赋给 创建好的二维数组
    for (int i = 1; i < sparse.length; i++) {
        int[] row = sparse[i];
        array[row[0]][row[1]]=row[2];
    }

    // 遍历二维数组,打印值
    for (int[] row : array) {
        for (int data : row) {
            System.out.print(data + "  ");
        }
        System.out.println();
    }
    return array;
}

稀疏数组转二维数组.png

原文链接:https://www.cnblogs.com/fzdkx/p/17317366.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:稀疏数组 - Python技术站

(0)
上一篇 2023年4月19日
下一篇 2023年4月20日

相关文章

  • Python实现的排列组合计算操作示例

    下面是详细讲解“Python实现的排列组合计算操作示例”的完整攻略。 1. 什么是排列组合 排列组合是数学中的一个分支,它研究是从组元素中选取若干个元素进行排列或组合的和规律。在实际应用中,排列组合经用计算概率、统计学、密码学等领域。 2. Python实现排列组计算 Python中有多种方法可以排列组合计算,以下是其中两种常用的方法。 2.1math库实现…

    python 2023年5月14日
    00
  • GPS北斗卫星时间同步系统助力电力自动化网络系统

    GPS北斗卫星时间同步系统助力电力自动化网络系统 GPS北斗卫星时间同步系统助力电力自动化网络系统 京准电子官微——ahjzsz 前言 近几年来,随着电力自动化水平的提高,在电力中计算机监控系统、微机保护装置、微机故障录波装置以及各类数据管理机得到了广泛的应用,而这些自动装置的配合工作需要有一个精确统一的时间。当电力系统发生故障时,既可实现全站各系统在统一时…

    算法与数据结构 2023年5月8日
    00
  • 浅析Python实现DFA算法

    下面是关于“浅析Python实现DFA算法”的完整攻略。 1. DFA算法简介 DFA(Deterministic Finite Automaton)算法是一种基于有限机的字符串匹配算法。它将模式串转换一个有限状态自动机,然后在文本串中按照状态自动的转移规则进行匹配,从实现高效的字符串匹配。 2. Python实现DFA算法 2.1算法流程 DFA算法的流如…

    python 2023年5月13日
    00
  • Python算法之栈(stack)的实现

    下面是详细讲解“Python算法之栈(stack)的实现”的完整攻略,包括栈的基本概念、Python实现和两个示例。 栈的基本概念 栈(stack)是一种线性数据结构,具有后进先出(IFO)的特点,即最进入的元素最先被访问。栈有两个基本操作:入栈(push)和出栈(pop)。入栈操作将元素添加到栈顶,出栈操作将栈顶元素移除并返回。栈还有一个重要的操作:看栈元…

    python 2023年5月14日
    00
  • C语言 超详细总结讲解二叉树的概念与使用

    C语言 超详细总结讲解二叉树的概念与使用 1. 什么是二叉树? 二叉树是一种树状数据结构,其中每个节点最多有两个子节点,被称为左子节点和右子节点。具有以下几个特点: 每个节点最多有两个子节点; 左子节点可以为空,右子节点也可以为空; 二叉树的每个节点最多有一个父节点; 二叉树通常定义为递归模式定义,即每个节点都可以看做一棵新的二叉树。 2. 二叉树的遍历方式…

    数据结构 2023年5月17日
    00
  • Java数据结构之图的路径查找算法详解

    Java数据结构之图的路径查找算法详解 什么是图? 在计算机科学中,图是一种非常常见的数据结构,用于表示图形和网络等概念。图由节点和边组成,其中节点表示实体,边表示这些实体之间的关系。节点和边可以表示各种各样的实体和关系,因此图在计算机科学中具有广泛的应用。 图的路径查找算法 路径查找算法是一个用途广泛的算法,它用于查找从一个节点到另一个节点的路径。在图中,…

    数据结构 2023年5月17日
    00
  • Python机器学习k-近邻算法(K Nearest Neighbor)实例详解

    下面是详细讲解“Python机器学习k-近邻算法(KNearestNeighbor)实例详解”的完整攻略,包括算法原理、Python实现和两个示例说明。 算法原理 k-近邻算法是一种基于实例的学习方法,其主要思想是通过计算样本之间的距离,找到与目标样本最近的k个样本,然后根据这k个样本的类进行分类。k-近邻算法的实现过程如下: 计算目标样本与训练样本之间的距…

    python 2023年5月14日
    00
  • Java数据结构之哈夫曼树概述及实现

    Java数据结构之哈夫曼树概述及实现 哈夫曼树概述 哈夫曼树(Huffman Tree),也称为最优树(Optimal Binary Tree),是一种带权路径长度最短的二叉树,也就是最小权重的前缀编码树。其基本思想是采用频率作为节点的权值,将频率较小的节点放在左子树上,频率较大的节点放在右子树上,从而形成一棵权值最小的二叉树。 实现过程 实现哈夫曼树需要以…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部