稀疏数组

  • 时间:
  • 来源:互联网
  • 文章标签:

稀疏数组

稀疏数组浪费大量空间,可以进行优化

例如:在这里插入图片描述

PS:稀疏数组可以和优化后的数组进行相互转换

(1)稀疏数组转换为优化后的数组

//计算稀疏数组中有多少有用的值
int sum = 0;
for (int i = 0; i < n; i++)	//n为稀疏数组的行
{
    for (int j = 0; j < m; j++)	//m为稀疏数组的列
    {
        if (arr[i][j] != 0)	//arr为稀疏数组
        {
            sum++;
        }
    }
}
//创建优化后的数组大小
int [][] arr2 = new int [sum + 1][3];
arr2[0][0] = n;	//存稀疏数组的行
arr2[0][1] = m;	//存稀疏数组的列
arr2[0][2] = sum;	//存稀疏数组有用的值的数量
int next = 1;
for (int i = 0; i < n; i++)	
{
    for (int j = 0; j < m; j++)	
    {
        if (arr[i][j] != 0)	
        {
            arr2[next][0] = i;
            arr2[next][1] = j;
            arr2[next][2] = arr[i][j];
            next++;
        }
    }
}

(2)优化后的数组转换回稀疏数组

int [][] arr = new int [arr2[0][0]][arr2[0][1]];
for (int i = 1; i <= arr2[0][2]; i++)
{
    arr[arr2[i][0]][arr2[i][1]] = arr2[i][2];
}

PS:今天这份稀疏数组优化的确优化了空间,但是牺牲了时间,具体看情况吧,就当作做笔记~

本文链接http://www.taodudu.cc/news/show-82973.html