# 稀疏矩陣

December 12, 2021

0 0 0 0 0 0
0 3 0 0 0 0
0 0 0 6 0 0
0 0 9 0 0 0
0 0 0 0 12 0

5 6 4

1 1 3
2 3 6
3 2 9
4 4 12

## 程式實作

``````#include <stdio.h>
#include <stdlib.h>

int main(void) {
int num[5][3] = {{5, 6, 4},
{1, 1, 3},
{2, 3, 6},
{3, 2, 9},
{4, 4, 12}};

int k = 1;
int i;
for(i = 0; i < num[0][0]; i++) {
int j;
for(j = 0; j < num[0][1]; j++) {
if(k <= num[0][2] &&
i == num[k][0] && j == num[k][1]) {
printf("%4d ", num[k][2]);
k++;
}
else
printf("%4d ", 0);
}
putchar('\n');
}

return 0;
}
``````
``````public class Matrix {
public static int[][] restore(int[][] sparse) {
int row = sparse[0][0];
int column = sparse[0][1];
int[][] array = new int[row][column];

for(int i = 0, k = 1; i < row; i++) {
for(int j = 0; j < column; j++) {
if(k <= sparse[0][2] &&
i == sparse[k][0] && j == sparse[k][1]) {
array[i][j] = sparse[k][2];
k++;
}
}
}

return array;
}

public static void main(String[] args) {
int[][] sparse = {{5, 6, 4},
{1, 1, 3},
{2, 3, 6},
{3, 2, 9},
{4, 4, 12}};

for(int[] arr : Matrix.restore(sparse)) {
for(int elm : arr) {
System.out.print(elm + " ");
}
System.out.println();
}
}
}
``````
``````def restore(sparse):
row = sparse[0][0]
column = sparse[0][1]
array = [[0] * column for i in range(row)]
k = 1
for i in range(row):
for j in range(column):
if k <= sparse[0][2] and \
i == sparse[k][0] and j == sparse[k][1]:
array[i][j] = sparse[k][2]
k += 1
return array

sparse = [
[5, 6, 4],
[1, 1, 3],
[2, 3, 6],
[3, 2, 9],
[4, 4, 12]
]
array = restore(sparse)
print(array)
``````
``````object Matrix {
def restore(sparse: Array[Array[Int]]) = {
val row = sparse(0)(0)
val column = sparse(0)(1)
val array = new Array[Array[Int]](row, column)
var k = 1
for(i <- 0 until row; j <- 0 until column) {
if(k <= sparse(0)(2) && i == sparse(k)(0) && j == sparse(k)(1)) {
array(i)(j) = sparse(k)(2)
k += 1
}
}
array
}
}

val sparse = Array(
Array(5, 6, 4),
Array(1, 1, 3),
Array(2, 3, 6),
Array(3, 2, 9),
Array(4, 4, 12)
)
Matrix.restore(sparse).foreach(arr => {
arr.foreach(elm => print(elm + " "))
println()
})
``````
``````def restore(sparse)
row = sparse[0][0]
column = sparse[0][1]
array = Array.new(row) {
Array.new(column, 0)
}
k = 1
row.times { |i|
column.times { |j|
if k <= sparse[0][2] &&
i == sparse[k][0] && j == sparse[k][1]
array[i][j] = sparse[k][2]
k += 1
end
}
}
array
end

sparse = [
[5, 6, 4],
[1, 1, 3],
[2, 3, 6],
[3, 2, 9],
[4, 4, 12]
]
array = restore(sparse)
p array
``````
``````function restore(sparse) {
let row = sparse[0][0];
let column = sparse[0][1];
let array = [];
for(let i = 0; i < row; i++) {
let lt = [];
lt.length = column;
lt.fill(0);
array.push(lt);
}

let k = 1;

for(let i = 0; i < row; i++) {
for(j = 0; j < column; j++) {
if(k <= sparse[0][2] && i == sparse[k][0] && j == sparse[k][1]) {
array[i][j] = sparse[k][2];
k += 1;
}
}
}

return array;
}

let sparse = [
[5, 6, 4],
[1, 1, 3],
[2, 3, 6],
[3, 2, 9],
[4, 4, 12]
];

console.log(restore(sparse));
``````
``````slice :: Int -> Int -> [a] -> [a]
slice start stop xs = take (stop - start) (drop start xs)

updated i j v mx =
let
row = mx !! i
updatedRow = (slice 0 j row) ++ [v] ++ (slice (j + 1) (length row) row)
before = slice 0 i mx
after = slice (i + 1) (length mx) mx
in before ++ [updatedRow] ++ after

restore sparse =
let
[row, column, n] = sparse !! 0
restored = replicate row \$ replicate column 0
in _restore (slice 1 (length sparse) sparse) restored

_restore (x:xs) restored =
let
[i, j, v] = x
nRestored = (updated i j v restored)
in
if null xs
then nRestored
else _restore xs (updated i j v restored)

main = print \$ restore [
[5, 6, 4],
[1, 1, 3],
[2, 3, 6],
[3, 2, 9],
[4, 4, 12]]
``````