稀疏数组的实现

谁践踏了优雅 2022-10-22 04:10 125阅读 0赞
  1. package sparsearray;
  2. /*
  3. *
  4. * 现在有一数组arr
  5. 0 0 0 0 0 0 0 0 0 0 0
  6. 0 0 1 0 0 0 0 0 0 0 0
  7. 0 0 0 2 0 0 0 0 0 0 0
  8. 0 0 0 0 0 0 0 0 0 0 0
  9. 0 0 0 0 0 0 0 0 0 0 0
  10. 0 0 0 0 0 0 0 0 0 0 0
  11. 0 0 0 0 0 0 0 0 0 0 0
  12. 0 0 0 0 0 0 0 0 0 0 0
  13. 0 0 0 0 0 0 0 0 0 0 0
  14. 0 0 0 0 0 0 0 0 0 0 0
  15. * 稀疏数组
  16. * 应用场景:棋盘(退出的时候暂时保存棋盘的当前状态),地图等
  17. * 概念:当一个数组大部分元素为0,或者同一个值的数组时,可以使用稀疏数组来保存该数组。
  18. * 处理方法:
  19. * 1)记录数组一共有几行几列,有多少个不同的值
  20. * 2) 把存储元素的行、列、值存储在一个小规模的数组中,从而缩小程序规模
  21. * 转换为稀疏数组sparseArr后
  22. * 行 列 值
  23. * 11 11 2
  24. * 1 2 1
  25. * 2 3 2
  26. * sparseArr[0][1] sparseArr[0][1] sparseArr[0][2]分别存储原二维数组的行、列、有值元素个数
  27. * 这样只需要3*3的二维数组就存储了原来11*11的二维数组存储的内容,大大节省了空间
  28. *
  29. *
  30. *
  31. *
  32. * */
  33. public class SparseArray {
  34. //初始化一个数组
  35. public static int[][] initArr(){
  36. int arr[][] = new int[11][11];
  37. for (int i = 0; i<11;i++){
  38. for (int j = 0; j<11;j++){
  39. arr[i][j] = 0;
  40. }
  41. }
  42. arr[1][2] = 1;
  43. arr[2][3] = 2;
  44. return arr;
  45. }
  46. public static void main(String[] args) {
  47. int arr[][] = initArr();
  48. int sparseArr[][] = toSparseArray(arr);
  49. printArr(sparseArr);
  50. int arr1[][] = toArr(sparseArr);
  51. printArr(arr1);
  52. }
  53. //二维数组转换为稀疏数组
  54. /*
  55. * 1.得到元素的数目num
  56. * 2.初始化一个数组sparseArr[num+1][3]
  57. * 3.遍历二维数组,把不为0的元素的行,列,值赋值给sparseArr[curPos]
  58. *
  59. * */
  60. public static int[][] toSparseArray(int arr[][]){
  61. int m = arr.length;
  62. int n = arr[0].length;
  63. int num = 0;
  64. for (int i=0;i<arr.length;i++){
  65. for (int j =0;j<arr[i].length;j++){
  66. if (arr[i][j]!=0){
  67. num++;
  68. }
  69. System.out.print(arr[i][j]+" ");
  70. }
  71. System.out.println();
  72. }
  73. int sparseArr[][] = new int[num+1][3];
  74. int curPos = 0;
  75. sparseArr[curPos++] = new int[]{ m,n,num};
  76. for (int i=0;i<arr.length;i++){
  77. for (int j =0;j<arr[i].length;j++){
  78. if (arr[i][j]!=0){
  79. sparseArr[curPos++]=new int[]{ i,j,arr[i][j]};
  80. }
  81. }
  82. }
  83. return sparseArr;
  84. }
  85. /*
  86. * 打印二维数组
  87. * */
  88. public static void printArr(int arr[][]){
  89. for (int i=0;i<arr.length;i++){
  90. for (int j =0;j<arr[i].length;j++){
  91. System.out.print(arr[i][j]+" " );
  92. }
  93. System.out.println();
  94. }
  95. }
  96. /*
  97. *
  98. * 稀疏数组转换为二维数组
  99. * 1.获取二维数组的行m和列n从稀疏数组的第一行获取sparseArr[0]
  100. * 2.初始化二维数组arr[m][n]
  101. * 3.遍历稀疏数组,给二维数组赋值
  102. *
  103. * */
  104. public static int[][] toArr(int sparseArr[][]){
  105. int m =sparseArr[0][0];
  106. int n = sparseArr[0][1];
  107. int [][]arr = new int[m][n];
  108. for (int i= 1;i<sparseArr.length;i++){
  109. //System.out.println(sparseArr[i][0] + " " + sparseArr[i][1] +" " +sparseArr[i][2]);
  110. arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
  111. }
  112. return arr;
  113. }
  114. }

发表评论

表情:
评论列表 (有 0 条评论,125人围观)

还没有评论,来说两句吧...

相关阅读

    相关 稀疏实现

    文章目录 目录 文章目录 前言 一 什么是稀疏数组? 二 稀疏数组怎么存储数据? 三 稀疏数组的实现 总结 --------------------

    相关 稀疏和队列

    一、稀疏 sparsearray 数组 1、先看一个实际的需求 编写的五子棋程序中,有存盘退出和续上盘的功能。 ![在这里插入图片描述][wate