Dada una array con la mayoría de sus elementos como 0, convierta esta array en array dispersa en C++
Ejemplos:
Input: Matrix: 0 1 1 1 2 2 2 1 3 3 2 5 4 3 4 Output: Sparse Matrix: 0 1 0 0 0 0 2 0 0 3 0 0 0 0 5 0 0 0 0 4 Explanation: Here the Sparse matrix is represented in the form Row Column Value Hence the row 0 1 1 means that the value of the matrix at row 0 and column 1 is 1
Acercarse:
- Obtenga la array con la mayoría de sus elementos como 0.
- Cree una nueva array 2D para almacenar la array dispersa de solo 3 columnas (fila, columna, valor).
- Iterar a través de Matrix y verificar si un elemento no es cero. En este caso, inserte este elemento en Sparse Matrix .
- Después de cada inserción, incremente el valor de longitud variable (aquí ‘len’). Esto servirá como la dimensión de fila de la array dispersa.
- Imprime la Dimensión de la Array Dispersa y sus elementos.
CPP
// C++ program to convert a Matrix
// into Sparse Matrix
#include <iostream>
using namespace std;
// Maximum number of elements in matrix
#define MAX 100
// Array representation
// of sparse matrix
//[][0] represents row
//[][1] represents col
//[][2] represents value
int data[MAX][3];
// total number of elements in matrix
int len;
// insert elements into sparse matrix
void insert(int r, int c, int val)
{
// insert row value
data[len][0] = r;
// insert col value
data[len][1] = c;
// insert element's value
data[len][2] = val;
// increment number of data in matrix
len++;
}
// printing Sparse Matrix
void print()
{
cout << "\nDimension of Sparse Matrix: "
<< len << " x " << 3;
cout << "\nSparse Matrix: \nRow Column Value\n";
for (int i = 0; i < len; i++) {
cout << data[i][0] << " "
<< data[i][1] << " "
<< data[i][2] << "\n";
}
}
// Driver code
int main()
{
int i, j;
int r = 5, c = 4;
// Get the matrix
int a[r] = { { 0, 1, 0, 0 },
{ 0, 0, 2, 0 },
{ 0, 3, 0, 0 },
{ 0, 0, 5, 0 },
{ 0, 0, 0, 4 } };
// print the matrix
cout << "\nMatrix:\n";
for (i = 0; i < r; i++) {
for (j = 0; j < c; j++) {
cout << a[i][j] << " ";
}
cout << endl;
}
// iterate through the matrix and
// insert every non zero elements
// in the Sparse Matrix
for (i = 0; i < r; i++)
for (j = 0; j < c; j++)
if (a[i][j] > 0)
insert(i, j, a[i][j]);
// Print the Sparse Matrix
print();
return 0;
}
Producción:
Matrix: 0 1 0 0 0 0 2 0 0 3 0 0 0 0 5 0 0 0 0 4 Dimension of Sparse Matrix: 5 x 3 Sparse Matrix: Row Column Value 0 1 1 1 2 2 2 1 3 3 2 5 4 3 4
Complejidad del tiempo : O(m*n) donde m es el número de filas y n es el número de columnas de la array
Espacio Auxiliar: O(MAX)