稀疏数组

引入

  • 当在网页上下棋类游戏时,玩到中途想要离开,但是我们需要保存进度,方便下次继续
  • 我们应该怎么实现 ?
    • 以围棋举例
      • 使用二维数组将棋盘记下 ,如 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深度学习人工智能BackPropagation链式法则

    Python深度学习人工智能BackPropagation链式法则 BackPropagation(反向传播)是深度学习中最常用的优化算法之一,它主要作用是通过代的方式,不断调整神经网络的权重和偏置,使得神经网络的损失函数最小化。本文将详细讲解BackPropagation的原理及Python实现,以及两个示例说明。 BackPropagation原理 Ba…

    python 2023年5月14日
    00
  • Python3.0 实现决策树算法的流程

    以下是关于“Python3.0实现决策树算法的流程”的完整攻略: 简介 决策树是一种常见的分类和回归算法,它可以用于处理离散和连续的数据。在本攻略中,我们将介绍如何使用Python3.0实现决策树算法,包括决策树的基本原理、决策树的实现方法、决策树的优化等。 决策树的基本原理 决策树的基本原理是通过对数据进行分割,将数据分成多个子集,每个子集对应一个决策节点…

    python 2023年5月14日
    00
  • C语言线性表的顺序表示与实现实例详解

    C语言线性表的顺序表示与实现实例详解 1. 线性表的定义 线性表是一种线性结构,它是由n个数据元素(n≥0)组成的有限序列。当n=0时,我们称为一个空表。 在C语言中,我们可以通过数组来实现线性表的顺序表示,每个数据元素都存在数组的一个位置中,数组下标可以看作是该数据元素的位置。 2. 线性表的基本操作 一个线性表的基本操作有以下几种: 2.1 初始化线性表…

    数据结构 2023年5月17日
    00
  • Python实现深度遍历和广度遍历的方法

    下面是详细讲解“Python实现深度遍历和广度遍历的方法”的完整攻略。 1. 什么是深度遍历和广度遍历? 深度遍历和广度遍历是图遍历中两种常用的方法。深遍是指从某个节点开始,沿着一条路径一直走到底,直到不能再走为止,然后回溯到上一个节点,走其他路径,直到遍历完整个图。广度遍历是指从某个节点开始,先遍该节点的所有邻居节点,然后历邻居节点的邻居节点,直到遍历完整…

    python 2023年5月14日
    00
  • python选择排序算法实例总结

    选择排序是一种简单但效率较低的排序算法,它的基本思想是每次从未排序的元素中选择最小的元素,然后将其放到已排序的元素末尾。在Python中,我们可以使用以下代码实现选择排序算法: def selection_sort(arr): n = len(arr) for i in range(n): min_idx = i for j in range(i+1, n)…

    python 2023年5月13日
    00
  • 浅谈Java数据结构之稀疏数组知识总结

    浅谈Java数据结构之稀疏数组知识总结 稀疏数组的定义 稀疏数组是指当一个数组中大部分元素是相同的值时,可以使用稀疏数组来保存该数组。稀疏数组的必要性在于节省内存空间,当数组中元素过多时,存储数组所需的内存空间也呈指数级增长。 稀疏数组的特点 稀疏数组存储的是一个原始的二维数组。 稀疏数组的第一行保存原始数组的基本信息,包括行数、列数、有效值的个数。 稀疏数…

    数据结构 2023年5月17日
    00
  • K-近邻算法的python实现代码分享

    下面是详细讲解“K-近邻算法的Python实现代码分享”的完整攻略。 K-近邻算法 K-近邻算法是一种常用的分类算法,其基本思想是在训练集中找到与测试样本最近的K个样本,然后根据这K个样本的类别投票,将测试样本归为票数最多的类别。 下面是一个Python实现K-近邻算法的示例: import numpy as np def knn(X_train, y_tr…

    python 2023年5月14日
    00
  • Python实现简单遗传算法(SGA)

    下面是详细讲解“Python实现简单遗传算法(SGA)”的完整攻略,包括算法原理、Python实现和两个示例说明。 算法原理 简单遗传算法(SGA)是一种基于自然选择和遗传进化的优化算法,其基本思想是通过模拟生物进化过程,不断优化的。SGA的步骤如下: 初始化种群,随机生成一组初始解。 评估种群中每个个体的度,根据适应度选择优的个体。 通过交叉和变异操作,产…

    python 2023年5月14日
    00
合作推广
合作推广
分享本页
返回顶部