稀疏数组 php

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

稀疏数组的处理方法;

1. 记录数组一共有几行几列，有多少个不同的值。
2. 把具有不同值的元素的行列有值记录在一个小规模的数组中，从而缩小程序的规模。

由7x6的数组转换成3x9的稀疏数组

<?php

// 稀疏数组
$arr = array();
$row = $col = 11;

// 创建个二维数组 填充 0
for ($i = 0; $i < 11; $i++) {
	for ($j = 0; $j < 11; $j++) {
		$arr[$i][$j] = 0;
	}
}

$arr[0][4] = 1;
$arr[2][3] = 1;
$arr[3][2] = 1;

echo "转换之前的数组
";
printArray($arr);

echo "转换后的数组
";
$arr = arrayToSparse($arr);
printArray($arr);

echo "转换回来
";
$arr = sparseToArray($arr);
printArray($arr);

// 转为稀疏数组 第一行分别是行数和列数 和有效非 0的总数
function arrayToSparse($arr)
{
	// 获取非的总数
	$sum = 0;
	foreach ($arr as $item) {
		foreach ($item as $v) {
			if ($v != 0) {
				$sum++;
			}
		}
	}
	$row = count($arr);
	$col = count($arr[0]);

	$sparseArray[0][0] = $row;
	$sparseArray[0][1] = $col;
	$sparseArray[0][2] = $sum;

	$count = 1;
	// 填充有效的 到稀疏数组中
	for ($i = 0; $i < $row; $i++) {
		for ($j = 0; $j < $col; $j++) {
			if ($arr[$i][$j] != 0) {
				$sparseArray[$count][0] = $i;
				$sparseArray[$count][1] = $j;
				$sparseArray[$count][2] = $arr[$i][$j];
				$count++;
			}
		}
	}

	return $sparseArray;

}

// 稀疏数组还原
function sparseToArray($arr)
{
	// 新建全 0 的数组
	$row = $arr[0][0];
	$col = $arr[0][1];
	$sum = $arr[0][2];

	$old = array();
	for ($i = 0; $i < $row; $i++) {
		for ($j = 0; $j < $col; $j++) {
			$old[$i][$j] = 0;
		}
	}

	// 填充有效的 1
	for ($i = 1; $i <= $sum; $i++) {
		$old[$arr[$i][0]][$arr[$i][1]] = $arr[$i][2];
	}

	return $old;

}


// 打印数组
function printArray($arr)
{
	foreach ($arr as $item) {
		foreach ($item as $v) {
			echo $v . "	";
		}
		echo "
";
	}
}

结果

╭─mac@macdeMacBook-Pro ~/www/未命名文件夹/test222 
╰─$ php index.php    
转换之前的数组
0	0	0	0	1	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	1	0	0	0	0	0	0	0
0	0	1	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
转换后的数组
11	11	3	
0	4	1	
2	3	1	
3	2	1	
转换回来
0	0	0	0	1	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	1	0	0	0	0	0	0	0
0	0	1	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
╭─mac@macdeMacBook-Pro ~/www/未命名文件夹/test222