Dada una array 2D y un conjunto de índices de celda, por ejemplo, una array de (i, j) donde i indica fila y j columna. Para cada índice de celda dado (i, j), encuentre las sumas de todos los elementos de la array excepto los elementos presentes en la i-ésima fila y/o la j-ésima columna.
Ejemplo:
mat[][] = { {1, 1, 2}
{3, 4, 6}
{5, 3, 2} }
Array of Cell Indexes: {(0, 0), (1, 1), (0, 1)}
Output: 15, 10, 16
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Una solución ingenua es considerar uno por uno todos los índices de celda dados. Para cada índice de celda (i, j), encuentre la suma de los elementos de la array que no están presentes ni en la i-ésima fila ni en la j-ésima columna. A continuación se muestra la implementación en C++ del enfoque Naive.
Implementación:
C++
#include<bits/stdc++.h>
#define R 3
#define C 3
using namespace std;
// A structure to represent a cell index
struct Cell
{
int r; // r is row, varies from 0 to R-1
int c; // c is column, varies from 0 to C-1
};
// A simple solution to find sums for a given array of cell indexes
void printSums(int mat[][C], struct Cell arr[], int n)
{
// Iterate through all cell indexes
for (int i=0; i<n; i++)
{
int sum = 0, r = arr[i].r, c = arr[i].c;
// Compute sum for current cell index
for (int j=0; j<R; j++)
for (int k=0; k<C; k++)
if (j != r && k != c)
sum += mat[j][k];
cout << sum << endl;
}
}
// Driver program to test above
int main()
{
int mat[][C] = {{1, 1, 2}, {3, 4, 6}, {5, 3, 2}};
struct Cell arr[] = {{0, 0}, {1, 1}, {0, 1}};
int n = sizeof(arr)/sizeof(arr[0]);
printSums(mat, arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int R = 3;
static int C = 3;
// A structure to represent a cell index
static class Cell
{
int r; // r is row, varies from 0 to R-1
int c; // c is column, varies from 0 to C-1
public Cell(int r, int c)
{
this.r = r;
this.c = c;
}
};
// A simple solution to find sums for
// a given array of cell indexes
static void printSums(int mat[][], Cell arr[], int n)
{
// Iterate through all cell indexes
for (int i = 0; i < n; i++)
{
int sum = 0, r = arr[i].r, c = arr[i].c;
// Compute sum for current cell index
for (int j = 0; j < R; j++)
{
for (int k = 0; k < C; k++)
{
if (j != r && k != c)
{
sum += mat[j][k];
}
}
}
System.out.println(sum);
}
}
// Driver code
public static void main(String[] args)
{
int mat[][] = {{1, 1, 2}, {3, 4, 6}, {5, 3, 2}};
Cell arr[] = {new Cell(0, 0), new Cell(1, 1), new Cell(0, 1)};
int n = arr.length;
printSums(mat, arr, n);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation of the approach # A structure to represent a cell index class Cell: def __init__(self, r, c): self.r = r # r is row, varies from 0 to R-1 self.c = c # c is column, varies from 0 to C-1 # A simple solution to find sums # for a given array of cell indexes def printSums(mat, arr, n): # Iterate through all cell indexes for i in range(0, n): Sum = 0; r = arr[i].r; c = arr[i].c # Compute sum for current cell index for j in range(0, R): for k in range(0, C): if j != r and k != c: Sum += mat[j][k] print(Sum) # Driver Code if __name__ == "__main__": mat = [[1, 1, 2], [3, 4, 6], [5, 3, 2]] R = C = 3 arr = [Cell(0, 0), Cell(1, 1), Cell(0, 1)] n = len(arr) printSums(mat, arr, n) # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
class GFG
{
static int R = 3;
static int C = 3;
// A structure to represent a cell index
public class Cell
{
public int r; // r is row, varies from 0 to R-1
public int c; // c is column, varies from 0 to C-1
public Cell(int r, int c)
{
this.r = r;
this.c = c;
}
};
// A simple solution to find sums for
// a given array of cell indexes
static void printSums(int [,]mat, Cell []arr, int n)
{
// Iterate through all cell indexes
for (int i = 0; i < n; i++)
{
int sum = 0, r = arr[i].r, c = arr[i].c;
// Compute sum for current cell index
for (int j = 0; j < R; j++)
{
for (int k = 0; k < C; k++)
{
if (j != r && k != c)
{
sum += mat[j,k];
}
}
}
Console.WriteLine(sum);
}
}
// Driver code
public static void Main(String[] args)
{
int [,]mat = {{1, 1, 2}, {3, 4, 6}, {5, 3, 2}};
Cell []arr = {new Cell(0, 0), new Cell(1, 1), new Cell(0, 1)};
int n = arr.Length;
printSums(mat, arr, n);
}
}
/* This code is contributed by PrinciRaj1992 */
Javascript
<script>
// javascript implementation of the approach
var R = 3;
var C = 3;
// A structure to represent a cell index
class Cell
{
constructor(r, c)
{
this.r = r;
this.c = c;
}
}
// A simple solution to find sums for
// a given array of cell indexes
function printSums(mat, arr , n) {
// Iterate through all cell indexes
for (i = 0; i < n; i++) {
var sum = 0, r = arr[i].r, c = arr[i].c;
// Compute sum for current cell index
for (j = 0; j < R; j++) {
for (k = 0; k < C; k++) {
if (j != r && k != c) {
sum += mat[j][k];
}
}
}
document.write(sum+"<br/>");
}
}
// Driver code
var mat = [ [ 1, 1, 2 ],
[ 3, 4, 6 ],
[ 5, 3, 2 ] ];
var arr = [ new Cell(0, 0), new Cell(1, 1), new Cell(0, 1) ];
var n = arr.length;
printSums(mat, arr, n);
// This code is contributed by aashish1995
</script>
Producción
15 10 16
La complejidad temporal de la solución anterior es O(n * R * C) donde n es el número de índices de celda dados y R x C es el tamaño de la array.
Una solución eficiente puede calcular todas las sumas en tiempo O(R x C+ n). La idea es calcular previamente la suma total, las filas y las columnas antes de procesar la array de índices dada. A continuación se muestran los detalles
- Calcule la suma de la array, llámela suma.
- Calcular la suma de filas y columnas individuales. (fila[] y columna[])
- Para un índice de celda (i, j), la suma deseada será “suma-fila[i] – col[j] + arr[i][j]”
A continuación se muestra la implementación de la idea anterior.
C++
// An efficient C++ program to compute sum for given array of cell indexes
#include<bits/stdc++.h>
#define R 3
#define C 3
using namespace std;
// A structure to represent a cell index
struct Cell
{
int r; // r is row, varies from 0 to R-1
int c; // c is column, varies from 0 to C-1
};
void printSums(int mat[][C], struct Cell arr[], int n)
{
int sum = 0;
int row[R] = {};
int col[C] = {};
// Compute sum of all elements, sum of every row and sum every column
for (int i=0; i<R; i++)
{
for (int j=0; j<C; j++)
{
sum += mat[i][j];
col[j] += mat[i][j];
row[i] += mat[i][j];
}
}
// Compute the desired sum for all given cell indexes
for (int i=0; i<n; i++)
{
int ro = arr[i].r, co = arr[i].c;
cout << sum - row[ro] - col[co] + mat[ro][co] << endl;
}
}
// Driver program to test above function
int main()
{
int mat[][C] = {{1, 1, 2}, {3, 4, 6}, {5, 3, 2}};
struct Cell arr[] = {{0, 0}, {1, 1}, {0, 1}};
int n = sizeof(arr)/sizeof(arr[0]);
printSums(mat, arr, n);
return 0;
}
Java
// An efficient Java program to compute
// sum for given array of cell indexes
class GFG
{
static int R = 3;
static int C = 3;
// A structure to represent a cell index
static class Cell
{
int r; // r is row, varies from 0 to R-1
int c; // c is column, varies from 0 to C-1
public Cell(int r, int c)
{
this.r = r;
this.c = c;
}
};
static void printSums(int mat[][],
Cell arr[], int n)
{
int sum = 0;
int []row = new int[R];
int []col = new int[C];
// Compute sum of all elements,
// sum of every row and sum every column
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
sum += mat[i][j];
col[j] += mat[i][j];
row[i] += mat[i][j];
}
}
// Compute the desired sum
// for all given cell indexes
for (int i = 0; i < n; i++)
{
int ro = arr[i].r, co = arr[i].c;
System.out.println(sum - row[ro] - col[co] +
mat[ro][co]);
}
}
// Driver Code
public static void main(String[] args)
{
int mat[][] = {{1, 1, 2},
{3, 4, 6},
{5, 3, 2}};
Cell arr[] = {new Cell(0, 0),
new Cell(1, 1),
new Cell(0, 1)};
int n = arr.length;
printSums(mat, arr, n);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation of the approach # A structure to represent a cell index class Cell: def __init__(self, r, c): self.r = r # r is row, varies from 0 to R-1 self.c = c # c is column, varies from 0 to C-1 # A simple solution to find sums # for a given array of cell indexes def printSums(mat, arr, n): Sum = 0 row, col = [0] * R, [0] * C # Compute sum of all elements, # sum of every row and sum every column for i in range(0, R): for j in range(0, C): Sum += mat[i][j] row[i] += mat[i][j] col[j] += mat[i][j] # Compute the desired sum # for all given cell indexes for i in range(0, n): r0, c0 = arr[i].r, arr[i].c print(Sum - row[r0] - col[c0] + mat[r0][c0]) # Driver Code if __name__ == "__main__": mat = [[1, 1, 2], [3, 4, 6], [5, 3, 2]] R = C = 3 arr = [Cell(0, 0), Cell(1, 1), Cell(0, 1)] n = len(arr) printSums(mat, arr, n) # This code is contributed by Rituraj Jain
C#
// An efficient C# program to compute
// sum for given array of cell indexes
using System;
class GFG
{
static int R = 3;
static int C = 3;
// A structure to represent a cell index
public class Cell
{
public int r; // r is row, varies from 0 to R-1
public int c; // c is column, varies from 0 to C-1
public Cell(int r, int c)
{
this.r = r;
this.c = c;
}
};
static void printSums(int [,]mat,
Cell []arr, int n)
{
int sum = 0;
int []row = new int[R];
int []col = new int[C];
// Compute sum of all elements,
// sum of every row and sum every column
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
sum += mat[i, j];
col[j] += mat[i, j];
row[i] += mat[i, j];
}
}
// Compute the desired sum
// for all given cell indexes
for (int i = 0; i < n; i++)
{
int ro = arr[i].r, co = arr[i].c;
Console.WriteLine(sum - row[ro] - col[co] +
mat[ro, co]);
}
}
// Driver Code
public static void Main(String[] args)
{
int [,]mat = {{1, 1, 2},
{3, 4, 6},
{5, 3, 2}};
Cell []arr = {new Cell(0, 0),
new Cell(1, 1),
new Cell(0, 1)};
int n = arr.Length;
printSums(mat, arr, n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// An efficient Javascript program to compute
// sum for given array of cell indexes
var R = 3;
var C = 3;
// A structure to represent a cell index
class Cell
{
// r is row, varies from 0 to R-1
// c is column, varies from 0 to C-1
constructor(r, c)
{
this.r = r;
this.c = c;
}
};
function printSums(mat, arr, n)
{
var sum = 0;
var row = Array(R).fill(0);
var col = Array(C).fill(0);
// Compute sum of all elements,
// sum of every row and sum every column
for (var i = 0; i < R; i++)
{
for (var j = 0; j < C; j++)
{
sum += mat[i][j];
col[j] += mat[i][j];
row[i] += mat[i][j];
}
}
// Compute the desired sum
// for all given cell indexes
for (var i = 0; i < n; i++)
{
var ro = arr[i].r, co = arr[i].c;
document.write(sum - row[ro] - col[co] +
mat[ro][co] + "<br>");
}
}
// Driver Code
var mat = [[1, 1, 2],
[3, 4, 6],
[5, 3, 2]];
var arr = [new Cell(0, 0),
new Cell(1, 1),
new Cell(0, 1)];
var n = arr.length;
printSums(mat, arr, n);
</script>
Producción
15 10 16
Complejidad Temporal: O(R x C+ n)
Espacio Auxiliar: O(R + C)
Gracias a Gaurav Ahirwar por sugerir esta solución eficiente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA