个人随笔
目录
稀疏数组
2022-03-23 18:00:35

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

定义

稀疏数组是一种二维数组。当在二维数组中存在较多的无意义的数如0的时候,我们可以考虑采用稀疏数组以节省空间。稀疏数组是一种n行3列的二维数组,arr[i][0]表示行,arr[i][1]表示列,arr[i][2]表示该位置对应的值。在对应的稀疏数组的arr[0][i]中记录的是对应的总数据数。即总行数、总列数、总的记录值数。

举例

稀疏数组的处理方式是:记录数组一共有几行几列,有多少个不同值;把具有不同值的元,如下上面是原始数组,下面是稀疏数组

  1. 0 0 0 0 0 0 0
  2. 0 0 1 0 0 0 0
  3. 0 0 0 2 0 0 0
  4. 0 0 0 0 0 4 0
  5. 0 0 0 0 0 0 0
  6. 5 7 3
  7. 1 2 1
  8. 2 3 2
  9. 3 5 4

稀疏数组行数为原始数组中不为0的元素数目+1,列为3,第一行是用来存放原数组有多少行,多少列,总共多少个有效元素,假设原数组有效元素个数为sum,则稀疏数组可以定义为int[][] sparseArray = new int[sum+1][3]

sparseArray[0][0]表示原数组有多少行
sparseArray[0][1]表示原数组有多少列
sparseArray[0][2]表示原数组有多少个有效元素
sparseArray[i][0],i>0表示第i个元素所在的行
sparseArray[i][1],i>0表示第i个元素所在的列
sparseArray[i][1],i>0表示第i个元素的值

这就是稀疏数组

Java版原始数组和稀疏数组的转换

  1. public class SparseArray {
  2. public static void main(String[] args) {
  3. //稀疏数组和原数组的互相转化
  4. //1、初始化原数组
  5. int[][] array = new int[5][7];
  6. //2、设置值
  7. array[1][2]=1;
  8. array[2][3]=2;
  9. array[3][5]=4;
  10. //打印
  11. System.out.println("原始数组如下:");
  12. printArray(array);
  13. //因为原始数组太稀疏了,浪费空间,所以要转变为稀疏数组,转换步骤如下
  14. //我们先来构造第一行的值
  15. //1、获取原数组的行
  16. int rowSize = array.length;
  17. //2、获取原数组的列
  18. int columnSize = array[0].length;
  19. //3、获取原数组的有效元素个数
  20. int sum = 0;
  21. for (int i = 0; i < array.length; i++) {
  22. int[] a = array[i];
  23. for (int j = 0; j < a.length; j++) {
  24. if(a[j]!=0) {
  25. sum++;
  26. }
  27. }
  28. }
  29. //构造稀疏数组
  30. int[][] sparseArray = new int[sum+1][3];
  31. //第一行第一列表示原始数组的行
  32. sparseArray[0][0]=rowSize;
  33. //第一行第二列表示原始数组的列
  34. sparseArray[0][1]=columnSize;
  35. //第一行第三列表示原始数组有效数据的数目
  36. sparseArray[0][2]=sum;
  37. //设置稀疏数组的值,从第2行开始放元素,每放一个就换行
  38. int row = 0;
  39. for (int i = 0; i < array.length; i++) {
  40. int[] a = array[i];
  41. for (int j = 0; j < a.length; j++) {
  42. if(a[j]!=0) {
  43. row++;
  44. //这是一个值,从上到下来遍历
  45. sparseArray[row][0] = i;
  46. sparseArray[row][1] = j;
  47. sparseArray[row][2] = a[j];
  48. }
  49. }
  50. }
  51. System.out.println("转换成稀疏数组如下:");
  52. printArray(sparseArray);
  53. //这里我们再来进行将稀疏数据转为原始数组,其实就是反向推到而已
  54. //1、获取数组有多少行
  55. int rowSizeBefore = sparseArray[0][0];
  56. int columnSizeBefore = sparseArray[0][1];
  57. //2、初始化数组
  58. int[][] arrayBefore = new int[rowSizeBefore][columnSizeBefore];
  59. //3、设置值
  60. for (int i = 1; i < sparseArray.length; i++) {
  61. arrayBefore[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
  62. }
  63. //还原后的数组
  64. System.out.println("还原后的数组:");
  65. printArray(arrayBefore);
  66. }
  67. /**
  68. * 打印数组
  69. * @param array
  70. */
  71. public static void printArray(int[][] array) {
  72. for (int i = 0; i < array.length; i++) {
  73. int[] a = array[i];
  74. for (int j = 0; j < a.length; j++) {
  75. System.out.print(a[j]+" ");
  76. }
  77. System.out.println();
  78. }
  79. }
  80. }

结果如下

  1. 原始数组如下:
  2. 0 0 0 0 0 0 0
  3. 0 0 1 0 0 0 0
  4. 0 0 0 2 0 0 0
  5. 0 0 0 0 0 4 0
  6. 0 0 0 0 0 0 0
  7. 转换成稀疏数组如下:
  8. 5 7 3
  9. 1 2 1
  10. 2 3 2
  11. 3 5 4
  12. 还原后的数组:
  13. 0 0 0 0 0 0 0
  14. 0 0 1 0 0 0 0
  15. 0 0 0 2 0 0 0
  16. 0 0 0 0 0 4 0
  17. 0 0 0 0 0 0 0
 20

啊!这个可能是世界上最丑的留言输入框功能~


当然,也是最丑的留言列表

有疑问发邮件到 : suibibk@qq.com 侵权立删
Copyright : 个人随笔   备案号 : 粤ICP备18099399号