首页 > 其他分享 >稀疏数组

稀疏数组

时间:2022-11-16 21:34:21浏览次数:40  
标签:int array2 稀疏 System 数组 println out

稀疏数组

  • 需求: 编写五子棋游戏中,有存盘退出和续上盘的功能。

  • 分析问题:因为该二维数组的很多值是默认值0,因此记录了很多没有意义的数据。
  • 解决:稀疏数组(一种数据结构)

稀疏数组介绍

  • 当一个数组中大部分元素为0,或者为同一值的数组时,可以使用稀疏数组来保存该数组

  • 稀疏数组的处理方式是:

    • 记录数组一共有几行几列,有多少个不同值

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

  • 如下图:左边是原始数组,右边是稀疏数组

  • package com.wang.array;
    
    import java.util.Arrays;
    
    public class ArrayDemo08 {
        public static void main(String[] args) {
            //1.创建一个二维数组 11*11   0:没有棋子  1:黑棋  2:白棋
            int[][] array1 = new int[11][11];
            array1[1][2] = 1;
            array1[2][3] = 2;
            //输出原始的数组
            System.out.println("输出原始的数组");
            for (int[] a : array1) {
                for (int b : a) {
                    System.out.print(b + "\t");
                }
                System.out.println();
            }
            System.out.println("======================");
            //转换为稀疏数组保存
            //1.获取有效值的个数
            int sum = 0;
            for (int i = 0; i < 11 ; i++) {
                for (int j = 0; j < 11 ; j++) {
                    if(array1[i][j] != 0){
                        sum++;
                    }
                }
            }
            System.out.println("有效值的个数:" + sum);
            //2.创建一个稀疏数组
            int[][] array2 = new int[sum+1][3];
            array2[0][0] = 11;
            array2[0][1] = 11;
            array2[0][2] = sum;
            //3.遍历二维数组,将非零的值,存在稀疏数组中
            int count = 0;
            for (int i = 0; i < array1.length; i++) {
                for (int j = 0; j < array1[i].length; j++) {
                    if (array1[i][j] != 0){
                        count++;
                        array2[count][0] = i;
                        array2[count][1] = j;
                        array2[count][2] = array1[i][j];
                    }
                }
            }
            //4.输出稀疏数组
            System.out.println("=============");
            for (int i = 0; i < array2.length; i++) {
                System.out.println(array2[i][0] + "\t"
                + array2[i][1] + "\t"
                + array2[i][2] + "\t");
            }
            //5.还原稀释数组
            System.out.println("=============");
            System.out.println("还原稀疏数组");
            //a.读取稀疏数组
            int[][] array3 = new int[array2[0][0]][array2[0][1]];
            //b.给其中的元素还原它的值
            //方法1:
    //        array3[array2[1][0]][array2[1][1]] = array2[1][2];
    //        array3[array2[2][0]][array2[2][1]] = array2[2][2];
            //方法2:
            for (int i = 1; i < array2.length; i++) {
                array3[array2[i][0]][array2[i][1]] = array2[i][2];
            }
            //打印还原后的二维数组
            System.out.println("打印还原后的二维数组");
            for (int[] a : array3) {
                for (int b : a) {
                    System.out.print(b + "\t");
                }
                System.out.println();
            }
        }
    }
    
    

标签:int,array2,稀疏,System,数组,println,out
From: https://www.cnblogs.com/wangzhizhi/p/16897576.html

相关文章

  • PHP数组知识点整理
    */*Copyright(c)2016,烟台大学计算机与控制工程学院*Allrightsreserved.*文件名:text.cpp*作者:常轩*微信公众号:Worldhello*完成日期:2016年8月11日*版本号:V1......
  • 数组~筛法求素数
    题目描述用筛法求之N内的素数。 用筛法求素数的基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列,1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后......
  • 数组~冒泡法排序
    题目描述用冒泡法对10个整数从小到大排序。输入10个整数输出排序好的10个整数样例输入4853234453453451223012样例输出341230458512223434......
  • 数组~插队
    题目描述有一个按照升序已排好的9个元素的数组,今输入一个数要求按原来排序的规律将它插入数组中。输入第一行,原始数列。第二行,需要插入的数字。输出排序后的数列......
  • 数组~明明的随机数
    题目描述明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N≤100),对于其中重复的数字,只保留一个,把其余相同的数......
  • #yyds干货盘点# LeetCode 腾讯精选练习 50 题:数组中的第K个最大元素
    题目:给定整数数组nums和整数k,请返回数组中第k个最大的元素。请注意,你需要找的是数组排序后的第k个最大的元素,而不是第k个不同的元素。你必须设计并实现时间复杂度......
  • leetcode26. 删除有序数组中的重复项(简单)
    题目:给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。由于在......
  • VUE对象数组,和普通数组的常用方法
    在VUE中也可以使用find,findIndex,map等方法对数组对象进行查询,赋值等操作,记录一下定义数组对象 vararrobj=[{"id":1,"keyword":"羽绒服","times":1000},{"id":2,"k......
  • Counting Rectangles(二维数组前缀和)
    题目链接题目描述:Youhave\(n\)rectangles,the\(i\)-threctanglehasheight\(h_i\)andwidth\(w_i\).Youareasked\(q\)queriesoftheform\(h_sw_sh_b......
  • 基础树状数组
    树状数组:利用数组下标的二进制关系,构造一种类似于树形的结构,有点像一个变成树形的前缀和可以实现单点修改、区间修改、区间查询等操作2的整数n次幂的位置就是表示该位置......